Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<vector>
- #include <string>
- #include<algorithm>
- #include <iostream>
- #include <queue>
- #include<set>
- #include<stack>
- #include<cmath>
- #include<math.h>
- #include<map>
- #include<unordered_map>
- #include<unordered_map>
- #include<ext/rope>
- using namespace std;
- using namespace __gnu_cxx;
- typedef long long ll;
- typedef pair<long long, long long> pll;
- #define mp make_pair
- #define fi(b, c) for(auto i = b; i <= c; i++)
- #define fj(b, c) for(auto j = b; j <= c; j++)
- #define fk(b, c) for(auto k = b; k <= c; k++)
- #define fq(b, c) for(auto q = b; q <= c; q++)
- #define fw(b, c) for(auto w = b; w <= c; w++)
- #define fim(b, c) for(auto i = b; i >= c; i--)
- #define fjm(b, c) for(auto j = b; j >= c; j--)
- #define fkm(b, c) for(auto k = b; k >= c; k--)
- #define all(a) a.begin(), a.end()
- #define rall(a) a.rbegin(), a.rend()
- #define sz(a) (ll)(a.size())
- #define fs first
- #define sd second
- #define endl "\n"
- #define cin(a) for(ll o = 0; o<a.size(); o++) cin>>a[o];
- #define cout(a) for(ll o = 0; o<a.size(); o++) cout<<a[o]<<" ";
- const ll inf = 1e9 + 123, llinf = 1e18 + 123;
- void xru(){
- // setlocale(LC_ALL, "rus");
- // freopen(".in", "r", stdin);
- // freopen(".out", "w", stdout);
- // ios_base::sync_with_stdio(false);
- // cin.tie(NULL);
- // cout.tie(NULL);
- }
- void run(){
- cout<<endl;
- system("pause");
- }
- ll MAXV = 2e5 + 123;
- ll n;
- vector<ll>t(4*MAXV), a(4*MAXV);
- ll left_son(ll v){ return 2 * v + 1; };
- ll right_son(ll v){ return 2 * v + 2; };
- void push(ll v, ll L, ll R){
- t[v] += a[v];
- a[left_son(v)] += a[v];
- a[right_son(v)] += a[v];
- a[v] = 0;
- }
- void relax(ll v, ll L, ll M, ll R){
- t[v] = max(t[left_son(v)] + a[left_son(v)],
- t[right_son(v)] + a[right_son(v)]);
- }
- void build(vector<ll>& base, ll v = 0, ll L = 0, ll R = n){
- // cout << L << " " << R << endl;
- a[v] = 0;
- if(R - L == 1){
- t[v] = base[L];
- return;
- }
- ll M = (L + R) / 2;
- build(base, left_son(v), L, M);
- build(base, right_son(v), M, R);
- relax(v, L, M, R);
- return;
- }
- void add(ll l, ll r, ll h, ll v = 0, ll L = 0, ll R = n){
- // cout << L << " " << R << endl;
- if( L >= l && R <= r){
- a[v] += h;
- return;
- }
- else if(L >= r || R <= l){
- return;
- }
- ll M = (L+R)/2;
- add(l, r, h, left_son(v), L, M);
- add(l, r, h, right_son(v), M, R);
- push(v, L, R);
- relax(v, L, M, R);
- }
- ll mx(ll l, ll r, ll v = 0, ll L = 0, ll R = n){
- // cout << L << " " << R << endl;
- if(L >= l && R <= r) {
- return t[v] + a[v];
- }
- if(L >= r || R <= l){
- return 0;
- }
- push(v, L, R);
- ll M = (L+R)/2;
- ll ans = max(mx(l, r, left_son(v), L, M) , mx(l, r, right_son(v), M, R));
- relax(v, L, M, R);
- return ans;
- }
- void print_tree(ll agg = 0, ll v = 0, ll L = 0, ll R = n){
- agg += a[v];
- if(R - L == 1){
- cout << L <<": " << t[v] + agg << endl;
- return;
- }
- ll M =(L+R)/2;
- print_tree(agg, left_son(v), L, M);
- print_tree(agg, right_son(v), M, R);
- }
- int main() {
- cin >> n;
- n+=2;
- ll k;
- cin >> k;
- vector<ll> base(n, 0);
- build(base);
- ll q;
- cin >> q;
- fi(0, q-1){
- ll l, r;
- cin >> l >> r;
- ll cnt = mx(l, r);
- // cout << k << " " << cnt << endl;
- if(k > cnt) cout << "1";
- else cout << "0";
- cout << endl;
- if(k > cnt) add(l, r, 1);
- // print_tree();
- }
- // run();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement