답안 #473564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
473564 2021-09-15T16:44:55 Z Haidara 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
619 ms 262148 KB
/** * * * * * * * * * * * * * **\
 *                             *
 *   Author: Haidara Nassour   *
 * Coded in: YYYY\M\D HH:MM:SS *
 *          Lang: C++          *
 *                             *
\** * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define itn int
#define rep(i,x,n) for(int i=(x);i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define per(i,x,n) for(int i=(x);i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define m(i,j) map< i , j >
#define um(i,j) unordered_map< i , j >
#define max_heap(i) priority_queue< i >
#define min_heap(i) priority_queue< i , vector< i > ,greater< i > >
#define ff first
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ss second
#define pp push_back
#define mini(x,y) x=min(x,y)
#define maxi(x,y) x=max(x,y)
#define debug(x) cout<<#x<<" ";
using namespace std;
using namespace __gnu_pbds;
void SIO(string name="")
{
    if(name!="")
    {
        freopen((name+".in").c_str(),"r",stdin);
        freopen((name+".out").c_str(),"w",stdout);
    }
}
template <class T> using o_set = tree<T, null_type, less<T>,rb_tree_tag, tree_order_statistics_node_update>;
///order_of_key = find index of element x ( returned val is integer )
///find_by_order = find value at index x ( returned val is pointer )
const double pi=2.0*acos(0.0);
const int inf=1LL<<62LL;
const int mod=1e9+7;
const int maxn=1000100;
struct node
{
    int sum,lazy,lc,rc,l,r;
    node():sum(0),lazy(0),rc(-1),lc(-1),l(0),r(1e9) {}
} st[maxn*4];
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)
{
    return st[st[inx].lc].sum+st[st[inx].rc].sum;
}
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 ;
    }
    if(st[inx].l>ur||ul>st[inx].r)
        return ;
    if(st[inx].lc==-1)
        create(inx,1);
    if(st[inx].rc==-1)
        create(inx,2);
    update(ul,ur,st[inx].lc);
    update(ul,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;
    if(ql>st[inx].r||st[inx].l>qr)
        return 0;
    if(st[inx].lc==-1)
        create(inx,1);
    if(st[inx].rc==-1)
        create(inx,2);
    int res=query(ql,qr,st[inx].lc)+query(ql,qr,st[inx].rc);
    st[inx].sum=push_up(inx);
    return res;
}
signed main()
{
    SIO("");
    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:52:21: warning: 'node::rc' will be initialized after [-Wreorder]
   52 |     int sum,lazy,lc,rc,l,r;
      |                     ^~
apple.cpp:52:18: warning:   'long long int node::lc' [-Wreorder]
   52 |     int sum,lazy,lc,rc,l,r;
      |                  ^~
apple.cpp:53:5: warning:   when initialized here [-Wreorder]
   53 |     node():sum(0),lazy(0),rc(-1),lc(-1),l(0),r(1e9) {}
      |     ^~~~
apple.cpp: In function 'void pull(long long int)':
apple.cpp:79:17: warning: unused variable 'mid' [-Wunused-variable]
   79 |             int mid=(st[inx].l+st[inx].r)/2;
      |                 ^~~
apple.cpp: In function 'void SIO(std::string)':
apple.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 188212 KB Output is correct
2 Correct 96 ms 188048 KB Output is correct
3 Correct 94 ms 188084 KB Output is correct
4 Correct 124 ms 188228 KB Output is correct
5 Correct 134 ms 188344 KB Output is correct
6 Correct 136 ms 188276 KB Output is correct
7 Correct 135 ms 188284 KB Output is correct
8 Correct 344 ms 189268 KB Output is correct
9 Correct 593 ms 190376 KB Output is correct
10 Correct 619 ms 190308 KB Output is correct
11 Correct 589 ms 190300 KB Output is correct
12 Correct 593 ms 190264 KB Output is correct
13 Runtime error 554 ms 262148 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -