Submission #391514

# Submission time Handle Problem Language Result Execution time Memory
391514 2021-04-19T06:38:33 Z ak2006 Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
510 ms 207680 KB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

struct node
{
    int l,r;
    ll sum,SET;
    node* nxtL;
    node* nxtR;
    node(){}
    node(int L,int R)
    {
        l = L,r = R;
        nxtL = NULL;
        nxtR = NULL;
        sum = SET = 0;
    }
};
void push(node* no)
{
    if (no->l == no->r)return;

    int l = no->l,r = no->r;
    int mid = (l + r)/2;

    if (!no->nxtL)no->nxtL = new node(l,mid);
    if (!no->nxtR)no->nxtR = new node(mid + 1,r);

    if (no->SET){

        no->nxtL->SET = no->nxtR->SET = no->SET;
        no->nxtL->sum = (no->SET) * (no->nxtL->r - no->nxtL->l + 1);
        no->nxtR->sum = (no->SET) * (no->nxtR->r - no->nxtR->l + 1);

        no->SET = 0;
    }
}
void setQ(node* no,int p,int q,ll v)
{
    if (no-> l > q or no->r < p)return;
    if (p <= no->l && no-> r <= q){
        no->sum = (no->r - no->l + 1) * v;
        no->SET = v;
        return;
    }
    push(no);

    setQ(no->nxtL,p,q,v);
    setQ(no->nxtR,p,q,v);

    no->sum = no->nxtL->sum + no->nxtR->sum;
}
ll sum(node* no,int p,int q)
{
    if (no->l > q or no->r < p)return 0;

    if (p <= no->l && no->r <= q)
        return no->sum;
    push(no);
    return sum(no->nxtL,p,q) + sum(no->nxtR,p,q);
}
int main()
{
    fast;
    int q,c = 0;
    cin>>q;
    node* root = new node(1,1e9);

    while (q--){
        int t,p,q;
        cin>>t>>p>>q;

        if (t == 1){
            c = sum(root,p + c,q + c);
            cout<<c<<'\n';
        }
        else{
            setQ(root,p + c,q + c,1);
        }
    }
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 16 ms 4940 KB Output is correct
5 Correct 20 ms 5964 KB Output is correct
6 Correct 20 ms 5964 KB Output is correct
7 Correct 19 ms 5960 KB Output is correct
8 Correct 151 ms 44504 KB Output is correct
9 Correct 307 ms 77380 KB Output is correct
10 Correct 323 ms 85376 KB Output is correct
11 Correct 334 ms 91672 KB Output is correct
12 Correct 332 ms 94592 KB Output is correct
13 Correct 295 ms 109988 KB Output is correct
14 Correct 300 ms 111064 KB Output is correct
15 Correct 510 ms 201692 KB Output is correct
16 Correct 489 ms 203184 KB Output is correct
17 Correct 301 ms 114756 KB Output is correct
18 Correct 312 ms 114900 KB Output is correct
19 Correct 492 ms 207664 KB Output is correct
20 Correct 500 ms 207680 KB Output is correct