Submission #338906

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338906	2020-12-24T08:24:19 Z	talant117408	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	674 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){
            (lz->left)->val = 1;
            (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){
            (lz->left)->val = 1;
            (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	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	29 ms	12524 KB	Output is correct
5	Correct	40 ms	15212 KB	Output is correct
6	Correct	36 ms	14592 KB	Output is correct
7	Correct	37 ms	15212 KB	Output is correct
8	Correct	291 ms	115948 KB	Output is correct
9	Correct	575 ms	200388 KB	Output is correct
10	Correct	674 ms	222060 KB	Output is correct
11	Correct	632 ms	238828 KB	Output is correct
12	Correct	653 ms	246252 KB	Output is correct
13	Runtime error	573 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-