Submission #338909

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338909	2020-12-24T08:28:28 Z	talant117408	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	699 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);
            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;
        }
        lz->val = 0;
    }
}

void update(node *root, node *lz, int l, int r, int ql, int qr){
    root->extend(l, r);
    lz->extend(l, r);
    push(root, lz, l, r);
    
    if(l > qr || ql > r) return;
    if(ql <= l && r <= qr){
        root->val = r-l+1;
        if(l != r){
            if(lz->left != NULL)
                (lz->left)->val = 1;
            if(lz->right != NULL)
                (lz->right)->val = 1;
        }
        return;
    }
    int mid = (l+r) >> 1;
    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){
    root->extend(l, r);
    lz->extend(l, r);
    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;
    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	30 ms	12524 KB	Output is correct
5	Correct	35 ms	15212 KB	Output is correct
6	Correct	35 ms	14572 KB	Output is correct
7	Correct	37 ms	15084 KB	Output is correct
8	Correct	320 ms	115820 KB	Output is correct
9	Correct	609 ms	200576 KB	Output is correct
10	Correct	653 ms	222120 KB	Output is correct
11	Correct	688 ms	239052 KB	Output is correct
12	Correct	699 ms	246392 KB	Output is correct
13	Runtime error	580 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-