oj.uz

답안 #502405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
502405 2022-01-05T21:40:22 Z daisy 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 59 ms 32152 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int m,num=1;
struct str
{
    int lkid,rkid,lazy,sum;
    str()
    {
        lkid=rkid=lazy=sum=0;
    }

}tree[1000005];
void update(int node,int l,int r,int le,int ri)
{
    if(!tree[node].lkid){num++;tree[node].lkid=num;}
    if(!tree[node].rkid){num++;tree[node].rkid=num;}
    if(tree[node].lazy)
    {
        tree[node].sum=(r-l+1);
        tree[tree[node].lkid].lazy=1;
        tree[tree[node].rkid].lazy=1;
        tree[node].lazy=0;
    }
    if(l>ri || r<le) return;
    if(l>=le && r<=ri)
    {
        tree[node].sum=(r-l+1);tree[node].lazy=1;
        return;
    }

    int mid=(l+r)/2;

    update(tree[node].lkid,l,mid,le,ri);
    update(tree[node].rkid,mid+1,r,le,ri);

    tree[node].sum=tree[tree[node].lkid].sum+tree[tree[node].rkid].sum;
}
int query(int node,int l,int r,int le,int ri)
{
    if(node==0) return 0;

    if(!tree[node].lkid){num++;tree[node].lkid=num;}
    if(!tree[node].rkid){num++;tree[node].rkid=num;}

    if(tree[node].lazy)
    {
        tree[node].sum=(r-l+1);
        tree[tree[node].lkid].lazy=1;
        tree[tree[node].rkid].lazy=1;
        tree[node].lazy=0;
    }
    if(l>ri || r<le) return 0;
    if(l>=le && r<=ri)
    {
        return tree[node].sum;
    }
    int mid=(l+r)/2;

    int r1=query(tree[node].lkid,l,mid,le,ri), r2=query(tree[node].rkid,mid+1,r,le,ri);
    tree[node].sum=tree[tree[node].lkid].sum+tree[tree[node].rkid].sum;

    return r1+r2;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    cin>>m;

    int t,a,b,c=0;

    for(int i=0;i<m;i++)
    {
        cin>>t>>a>>b;
        a+=c;b+=c;

        if(t==2)
        {
            update(1,1,1000000000,a,b);
        }
        if(t==1)
        {
            c=query(1,1,1000000000,a,b);
            cout<<c<<endl;
        }
    }

}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 8 ms 15948 KB Output is correct
3 Correct 8 ms 15964 KB Output is correct
4 Correct 18 ms 15972 KB Output is correct
5 Correct 20 ms 15976 KB Output is correct
6 Correct 20 ms 15948 KB Output is correct
7 Correct 19 ms 15992 KB Output is correct
8 Runtime error 59 ms 32152 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -