Submission #338912

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338912	2020-12-24T08:42:57 Z	talant117408	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	765 ms	262148 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;
    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, *Lazy;

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

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

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

int main(){
    do_not_disturb
    
    Root = new node(1, mod);
    Lazy = 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, Lazy, 1, mod, l, r);
            cout << ans << endl;
            last = ans;
        }
        else{
            update(Root, Lazy, 1, mod, l, r);
        }
    }
    
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	23 ms	6380 KB	Output is correct
5	Correct	29 ms	7788 KB	Output is correct
6	Correct	28 ms	7532 KB	Output is correct
7	Correct	29 ms	7788 KB	Output is correct
8	Correct	291 ms	58220 KB	Output is correct
9	Correct	478 ms	100716 KB	Output is correct
10	Correct	499 ms	111340 KB	Output is correct
11	Correct	494 ms	119832 KB	Output is correct
12	Correct	513 ms	123372 KB	Output is correct
13	Correct	479 ms	144364 KB	Output is correct
14	Correct	474 ms	145644 KB	Output is correct
15	Runtime error	765 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-