Submission #338914

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338914	2020-12-24T08:46:30 Z	talant117408	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	541 ms	137836 KB

apple

/*
    Code written by Talant I.D.
*/
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

struct node{
    int val;
    int prop;
    node *left, *right;
    
    node(int l, int r){
        val = 0;
        left = NULL;
        right = NULL;
    }
    
    void extend(int l, int r){
        if(left == NULL){
            int mid = (l+r) >> 1;
            left = new node(l, mid);
        }
        if(right == NULL){
            int mid = (l+r) >> 1;
            right = new node(mid+1, r);
        }
    }
};

node *Root;

void push(node *root, int l, int r){
    if(root->prop){
        root->val = r-l+1;
        if(l != r){
            if(root->left != NULL)
                (root->left)->prop = 1;
            if(root->right != NULL)
                (root->right)->prop = 1;
        }
    }
}

void update(node *root, int l, int r, int ql, int qr){
    push(root, l, r);
    if(l > qr || ql > r) return;
    if(ql <= l && r <= qr){
        root->prop = 1;
        push(root, l, r);
        return;
    }
    
    int mid = (l+r) >> 1;
    root->extend(l, r);
    push(root, l, r);
    
    update(root->left, l, mid, ql, qr);
    update(root->right, mid+1, r, ql, qr);
    root->val = (root->left)->val+(root->right)->val;
}

int get(node *root, int l, int r, int ql, int qr){
    push(root, l, r);
    if(l > qr || ql > r) return 0;
    if(ql <= l && r <= qr) return root->val;
    
    int mid = (l+r) >> 1;
    root->extend(l, r);
    push(root, l, r);
    
    return get(root->left, l, mid, ql, qr)+get(root->right, mid+1, r, ql, qr);
}

int main(){
    do_not_disturb
    
    Root = new node(1, mod);
    
    int q;
    cin >> q;
    int last = 0;
    while(q--){
        int type, l, r;
        cin >> type >> l >> r;
        l += last;
        r += last;
        if(type == 1){
            auto ans = get(Root, 1, mod, l, r);
            cout << ans << endl;
            last = ans;
        }
        else{
            update(Root, 1, mod, l, r);
        }
    }
    
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	21 ms	3436 KB	Output is correct
5	Correct	22 ms	4076 KB	Output is correct
6	Correct	21 ms	3948 KB	Output is correct
7	Correct	22 ms	4100 KB	Output is correct
8	Correct	193 ms	29328 KB	Output is correct
9	Correct	353 ms	50740 KB	Output is correct
10	Correct	384 ms	56008 KB	Output is correct
11	Correct	373 ms	60268 KB	Output is correct
12	Correct	404 ms	62088 KB	Output is correct
13	Correct	343 ms	72300 KB	Output is correct
14	Correct	346 ms	72940 KB	Output is correct
15	Correct	521 ms	133868 KB	Output is correct
16	Correct	528 ms	134892 KB	Output is correct
17	Correct	350 ms	76056 KB	Output is correct
18	Correct	353 ms	75884 KB	Output is correct
19	Correct	541 ms	137836 KB	Output is correct
20	Correct	540 ms	137836 KB	Output is correct