답안 #593501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593501	2022-07-11T09:46:28 Z	fdnfksd	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	252 ms	139468 KB

apple

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll maxN=5e5;
struct node
{
    ll l=0,r=0, val=0;
}st[maxN*50];
ll lazy[50*maxN];
ll nnode=1;
bool inter(ll x, ll y, ll i, ll j)
{
    if(y<i||j<x) return false;
    return true;
}
void down(ll id,ll l, ll r)
{
    if(lazy[id]>0)
    {
        lazy[id]=0;
        ll mid=l+r>>1;
        ll idl=st[id].l;
        ll idr=st[id].r;
        st[idl].val=mid-l+1;
        lazy[idl]=1;
        st[idr].val=r-mid;
        lazy[idr]=1;
    }
}
void update(ll id, ll l, ll r,ll i, ll j)
{
    if(!inter(l,r,i,j)) return;
    if(i<=l&&r<=j)
    {
        st[id].val=r-l+1;
        lazy[id]=1;
        return;
    }
    ll mid=l+r>>1;
    if(st[id].l==0)
    {
        st[id].l=++nnode;
        st[id].r=++nnode;
    }
    down(id,l,r);
    update(st[id].l,l,mid,i,j);
    update(st[id].r,mid+1,r,i,j);
    st[id].val=st[st[id].l].val+st[st[id].r].val;
}

ll get(ll id, ll l, ll r, ll i, ll j)
{
    if(i<=l&&r<=j)
    {
        //cout << id<<' ';
        return st[id].val;

    }
    ll mid=l+r>>1;
    //ll mid=l+r>>1;
    if(inter(l,r,i,j))
    {
        if(st[id].l>0&&st[id].r>0)
        {
            down(id,l,r);
            return  get(st[id].l,l,mid,i,j)+ get(st[id].r,mid+1,r,i,j);
        }
        else
        {
            st[id].l=++nnode;
            st[id].r=++nnode;
            down(id,l,r);
            return  get(st[id].l,l,mid,i,j)+ get(st[id].r,mid+1,r,i,j);
        }
    }
    else return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll m;
    cin >> m;
    ll c=0;
    for(int i=1;i<=m;i++)
    {
        ll x, y, type;
        cin >> type;
        if(type==2)
        {
            cin >> x >> y;
            update(1,1,1e9,x+c,y+c);
        }
        else
        {
            cin >> x >> y;
            c=get(1,1,1e9,x+c,y+c);
            cout << c<<'\n';
        }
    }

}

Compilation message

apple.cpp: In function 'void down(ll, ll, ll)':
apple.cpp:21:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         ll mid=l+r>>1;
      |                ~^~
apple.cpp: In function 'void update(ll, ll, ll, ll, ll)':
apple.cpp:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     ll mid=l+r>>1;
      |            ~^~
apple.cpp: In function 'll get(ll, ll, ll, ll, ll)':
apple.cpp:59:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	9 ms	3412 KB	Output is correct
5	Correct	12 ms	4160 KB	Output is correct
6	Correct	11 ms	4024 KB	Output is correct
7	Correct	11 ms	4180 KB	Output is correct
8	Correct	79 ms	30192 KB	Output is correct
9	Correct	177 ms	52400 KB	Output is correct
10	Correct	174 ms	57688 KB	Output is correct
11	Correct	179 ms	61900 KB	Output is correct
12	Correct	183 ms	63876 KB	Output is correct
13	Correct	161 ms	74212 KB	Output is correct
14	Correct	156 ms	74972 KB	Output is correct
15	Correct	252 ms	135628 KB	Output is correct
16	Correct	243 ms	136508 KB	Output is correct
17	Correct	159 ms	77540 KB	Output is correct
18	Correct	159 ms	77544 KB	Output is correct
19	Correct	239 ms	139468 KB	Output is correct
20	Correct	232 ms	139464 KB	Output is correct