Submission #919588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919588	2024-02-01T07:54:18 Z	Khanhcsp2	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	384 ms	207984 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	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	14 ms	4952 KB	Output is correct
5	Correct	12 ms	5980 KB	Output is correct
6	Correct	15 ms	5716 KB	Output is correct
7	Correct	11 ms	6016 KB	Output is correct
8	Correct	97 ms	44624 KB	Output is correct
9	Correct	209 ms	77240 KB	Output is correct
10	Correct	230 ms	85328 KB	Output is correct
11	Correct	226 ms	91472 KB	Output is correct
12	Correct	230 ms	94212 KB	Output is correct
13	Correct	213 ms	109904 KB	Output is correct
14	Correct	199 ms	111136 KB	Output is correct
15	Correct	384 ms	201844 KB	Output is correct
16	Correct	368 ms	203088 KB	Output is correct
17	Correct	215 ms	114768 KB	Output is correct
18	Correct	205 ms	114768 KB	Output is correct
19	Correct	363 ms	207576 KB	Output is correct
20	Correct	363 ms	207984 KB	Output is correct