oj.uz

답안 #502403

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
502403 2022-01-05T21:37:33 Z daisy 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 247 ms 160784 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[5000005];
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 36 ms 78496 KB Output is correct
2 Correct 36 ms 78532 KB Output is correct
3 Correct 37 ms 78540 KB Output is correct
4 Correct 51 ms 78680 KB Output is correct
5 Correct 56 ms 78636 KB Output is correct
6 Correct 49 ms 78584 KB Output is correct
7 Correct 49 ms 78596 KB Output is correct
8 Correct 134 ms 78800 KB Output is correct
9 Correct 247 ms 78908 KB Output is correct
10 Correct 227 ms 80636 KB Output is correct
11 Correct 247 ms 80776 KB Output is correct
12 Correct 235 ms 80648 KB Output is correct
13 Correct 210 ms 81016 KB Output is correct
14 Correct 219 ms 81088 KB Output is correct
15 Runtime error 218 ms 160784 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -