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

apple

#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;
}

Subtask #1

100.0 / 100.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