Submission #391514

#	Time	Username	Problem	Language	Result	Execution time	Memory
391514		ak2006	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	510 ms	207680 KiB

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