oj.uz

답안 #473604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
473604 2021-09-15T17:15:19 Z Haidara 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 586 ms 186844 KB 
/** * * * * * * * * * * * * * **\
 *                             *
 *   Author: Haidara Nassour   *
 * Coded in: YYYY\M\D HH:MM:SS *
 *          Lang: C++          *
 *                             *
\** * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int maxn=123456;
struct node
{
    int sum,lazy,lc,rc,l,r;
    node():sum(0),lazy(0),rc(-1),lc(-1),l(0),r(1e9) {}
} st[maxn*64];
int nodecnt=2;
void create(int inx,int child)
{
    int mid=(st[inx].l+st[inx].r)/2;
    if(child==1)
    {
        st[inx].lc=nodecnt++;
        st[st[inx].lc].l=st[inx].l;
        st[st[inx].lc].r=mid;
    }
    else
    {
        st[inx].rc=nodecnt++;
        st[st[inx].rc].l=mid+1;
        st[st[inx].rc].r=st[inx].r;
    }
}
void pull(int inx)
{
    if(st[inx].lazy)
    {
        st[inx].sum=st[inx].r-st[inx].l+1;
        if(st[inx].l!=st[inx].r)
        {
            int mid=(st[inx].l+st[inx].r)/2;
            if(st[inx].lc==-1)
                create(inx,1);
            if(st[inx].rc==-1)
                create(inx,2);
            st[st[inx].lc].lazy=1;
            st[st[inx].rc].lazy=1;
        }
    }
    st[inx].lazy=0;
}
int push_up(int inx)
{
    int res1=st[st[inx].lc].sum;
    int res2=st[st[inx].rc].sum;
    if(st[st[inx].lc].lazy)
        res1=(st[inx].l+st[inx].r)/2-st[inx].l+1;
    if(st[st[inx].rc].lazy)
        res2=st[inx].r-(st[inx].l+st[inx].r)/2;
    return res1+res2;
}
void update(int ul,int ur,int inx)
{
    pull(inx);
    if(ul==st[inx].l&&st[inx].r==ur)
    {
        st[inx].lazy=1;
        pull(inx);
        return ;
    }
    int mid=(st[inx].l+st[inx].r)/2;
    if(st[inx].lc==-1)
        create(inx,1);
    if(st[inx].rc==-1)
        create(inx,2);
    if(ul>mid)
        update(ul,ur,st[inx].rc);
    else if(ur<mid+1)
        update(ul,ur,st[inx].lc);
    else
    {
        update(ul,mid,st[inx].lc);
        update(mid+1,ur,st[inx].rc);
    }
    st[inx].sum=push_up(inx);
}
int query(int ql,int qr,int inx)
{
    pull(inx);
    if(ql==st[inx].l&&st[inx].r==qr)
        return st[inx].sum;
    int mid=(st[inx].l+st[inx].r)/2;
    if(st[inx].lc==-1)
        create(inx,1);
    if(st[inx].rc==-1)
        create(inx,2);
    int res=0;
    if(ql>mid)
        res=query(ql,qr,st[inx].rc);
    else if(qr<mid+1)
        res=query(ql,qr,st[inx].lc);
    else
        res=query(ql,mid,st[inx].lc)+query(mid+1,qr,st[inx].rc);
    st[inx].sum=push_up(inx);
    return res;
}
signed main()
{
    int q;
    cin>>q;
    int c=0;
    while(q--)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int j,k;
            cin>>j>>k;
            c=query(j+c,k+c,1);
            cout<<c<<endl;
        }
        else
        {
            int j,k;
            cin>>j>>k;
            update(j+c,k+c,1);
        }
    }
}

Compilation message

apple.cpp: In constructor 'node::node()':
apple.cpp:14:21: warning: 'node::rc' will be initialized after [-Wreorder]
   14 |     int sum,lazy,lc,rc,l,r;
      |                     ^~
apple.cpp:14:18: warning:   'int node::lc' [-Wreorder]
   14 |     int sum,lazy,lc,rc,l,r;
      |                  ^~
apple.cpp:15:5: warning:   when initialized here [-Wreorder]
   15 |     node():sum(0),lazy(0),rc(-1),lc(-1),l(0),r(1e9) {}
      |     ^~~~
apple.cpp: In function 'void pull(int)':
apple.cpp:41:17: warning: unused variable 'mid' [-Wunused-variable]
   41 |             int mid=(st[inx].l+st[inx].r)/2;
      |                 ^~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 185704 KB Output is correct
2 Correct 89 ms 185720 KB Output is correct
3 Correct 89 ms 185748 KB Output is correct
4 Correct 114 ms 185784 KB Output is correct
5 Correct 121 ms 185768 KB Output is correct
6 Correct 119 ms 185832 KB Output is correct
7 Correct 119 ms 185924 KB Output is correct
8 Correct 284 ms 185956 KB Output is correct
9 Correct 496 ms 186168 KB Output is correct
10 Correct 508 ms 186156 KB Output is correct
11 Correct 500 ms 186264 KB Output is correct
12 Correct 509 ms 186132 KB Output is correct
13 Correct 480 ms 186308 KB Output is correct
14 Correct 494 ms 186300 KB Output is correct
15 Correct 583 ms 186624 KB Output is correct
16 Correct 579 ms 186564 KB Output is correct
17 Correct 501 ms 186692 KB Output is correct
18 Correct 502 ms 186844 KB Output is correct
19 Correct 586 ms 186632 KB Output is correct
20 Correct 584 ms 186576 KB Output is correct