oj.uz

답안 #918727

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918727 2024-01-30T10:04:27 Z AndrijaM 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 45 ms 188248 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = (int)3e5+10;
int mx=1e9, st[maxn*40], lz[maxn*40];
int L[maxn*40], R[maxn*40], IND = 1, q,c;

void prop(int pos,int l,int r)
{
    if(!pos || lz[pos]!=1)
    {
        return ;
    }
    if(lz[pos]==1)
    {
        st[pos]=lz[pos]*(r-l+1);
        if(l!=r)
        {
            if(!L[pos])L[pos]=++IND;
            if(!R[pos])R[pos]=++IND;
            lz[L[pos]]=lz[R[pos]]=lz[pos];
        }
        lz[pos]=0;
    }
}

void u(int i,int j,int l,int r,int val,int pos)
{
    if(!pos || i>j)
    {
        return ;
    }
    if(i>r || j<l)
    {
        return ;
    }
    prop(pos,l,r);
	if(i<=l && r<=j)
    {
        st[pos]=(r-l+1)*val;
        if(l!=r)
        {
            if(!L[pos])L[pos]=++IND;
            if(!R[pos])R[pos]=++IND;
            lz[L[pos]]=lz[R[pos]]=val;
        }
        return ;
    }
    int mid=(l+r)/2;
    if(i<=mid)
    {
        if(!L[pos])L[pos]=++IND;
        u(i,j,l,mid,val,L[pos]);
    }
    if(j>mid)
    {
        if(!R[pos])R[pos]=++IND;
        u(i,j,mid+1,r,val,R[pos]);
    }
    st[pos]=st[L[pos]]+st[R[pos]];
}

int query(int i,int j,int l,int r,int pos)
{
    if(!pos || i>j)
    {
        return 0;
    }
    if(i>r || j<l)
    {
        return 0;
    }
	prop(pos,l,r);
	if(i<=l && r<=j)
    {
        return st[pos];
    }
    int mid=(l+r)/2;
    return query(i,j,l,mid,L[pos])+query(i,j,mid+1,r,R[pos]);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> q;
    memset(lz,0,sizeof(lz));
    memset(st,0,sizeof st);
    memset(L,0,sizeof L);
    memset(R,0,sizeof R);
    while(q--){
        int t, x, y; cin >> t >> x >> y; x+=c, y+=c;
        if(t==1) c = query(x,y,1,mx,1), cout << c <<endl;
        else u(x,y,1,mx,1,1);
    }
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 188240 KB Output is correct
2 Correct 43 ms 188248 KB Output is correct
3 Incorrect 45 ms 188244 KB Output isn't correct
4 Halted 0 ms 0 KB -