Submission #791596

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
791596	2023-07-24T07:49:34 Z	alittlemiddle	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	320 ms	207756 KB

apple

#include <bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=1e5+11;
int q;
struct node
{
    int sum, lazy;
    node* l;
    node* r;
    node()
    {
        l=r=NULL;
        sum=lazy=0;
    }
};
node* root;
void down(node* pos, int l, int r)
{
    if(pos->lazy==0) return;
    int mid=(l+r)>>1;
    pos->l->lazy=pos->lazy;
    pos->r->lazy=pos->lazy;
    pos->l->sum=(pos->lazy)*(mid-l+1);
    pos->r->sum=(pos->lazy)*(r-mid);
}
void update(node* pos, int l, int r, int u, int v, int val)
{
    if(l>v||r<u) return;
    if(u<=l && r<=v)
    {
        pos->sum=val*(r-l+1);
        pos->lazy=val;
        return;
    }
    if(pos->l==NULL) pos->l = new node();
    if(pos->r==NULL) pos->r = new node();
    int mid=(l+r)>>1;
    down(pos, l, r);
    update(pos->l, l, mid, u, v, val);
    update(pos->r, mid+1, r, u, v, val);
    pos->sum=pos->l->sum+pos->r->sum;
}
int get(node* pos, int l, int r, int u, int v)
{
    if(l>v||r<u) return 0;
    if(u<=l && r<=v)
    {
        return pos->sum;
    }
    if(pos->l==NULL) pos->l = new node();
    if(pos->r==NULL) pos->r = new node();
    down(pos, l, r);
    int mid=(l+r)>>1;
    return get(pos->l, l, mid, u, v)+get(pos->r, mid+1, r, u, v);
}
void sol()
{
    cin >> q;
    int c=0;
    root = new node();
    while(q--)
    {
        int tt, x, y;
        cin >> tt >> x >> y;
        x+=c;
        y+=c;
        if(tt==1)
        {
            int ans=get(root, 1, 1e9, x, y);
            c=ans;
            cout << ans << el;
        }
        else
        {
            update(root, 1, 1e9, x, y, 1);
        }
    }
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	9 ms	4936 KB	Output is correct
5	Correct	11 ms	5964 KB	Output is correct
6	Correct	11 ms	5788 KB	Output is correct
7	Correct	11 ms	5924 KB	Output is correct
8	Correct	103 ms	44620 KB	Output is correct
9	Correct	192 ms	77312 KB	Output is correct
10	Correct	192 ms	85432 KB	Output is correct
11	Correct	215 ms	91672 KB	Output is correct
12	Correct	201 ms	94512 KB	Output is correct
13	Correct	181 ms	109944 KB	Output is correct
14	Correct	182 ms	111000 KB	Output is correct
15	Correct	305 ms	201704 KB	Output is correct
16	Correct	300 ms	203200 KB	Output is correct
17	Correct	205 ms	114812 KB	Output is correct
18	Correct	231 ms	114880 KB	Output is correct
19	Correct	305 ms	207756 KB	Output is correct
20	Correct	320 ms	207660 KB	Output is correct