Submission #875578

#	Time	Username	Problem	Language	Result	Execution time	Memory
875578		CYhuang	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	31 ms	50812 KiB

apple

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long

#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rof(i,a,b) for(int i=a;i>=b;i--)

typedef pair<int,int> pii;
#define F first
#define S second

typedef vector<int> vi;
#define pb push_back
#define ft front()
#define bk back()
#define tp top()
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define ms(a,x) memset(a,x,sizeof(a))

#define lc p<<1
#define rc (p<<1)|1
const int Size=1e6;
struct Node{
    int len,cnt,tg;
}seg[4*Size+20],init;
Node add(Node nd1,Node nd2){
    Node nd;
    nd.len=nd1.len+nd2.len;
    nd.tg=nd1.tg&nd2.tg;
    nd.cnt=(nd1.tg?nd1.len:nd1.cnt)+(nd2.tg?nd2.len:nd2.cnt);
    return nd;
}
void setnode(int p,int val){
    seg[p].tg+=val;
}
void push_up(int p){
    seg[p]=add(seg[lc],seg[rc]);
}
void push_down(int p){
    if(seg[p].tg){
        setnode(lc,seg[p].tg);
        setnode(rc,seg[p].tg);
    }
}
void build(int s,int t,int p){
    if(s==t){
        seg[p].len=1;
        return ;
    }
    int m=s+((t-s)>>1);
    build(s,m,lc);
    build(m+1,t,rc);
    push_up(p);
}
void modify(int l,int r,int s,int t,int p,int val){
    if(l<=s&&t<=r){
        setnode(p,val);
        return ;
    }
    push_down(p);
    int m=s+((t-s)>>1);
    if(l<=m)    modify(l,r,s,m,lc,val);
    if(m<r) modify(l,r,m+1,t,rc,val);
    push_up(p);
}
Node query(int l,int r,int s,int t,int p){
    if(l<=s&&t<=r)  return seg[p];
    int m=s+((t-s)>>1);
    push_down(p);
    Node res=init;
    if(l<=m)    res=add(res,query(l,r,s,m,lc));
    if(m<r) res=add(res,query(l,r,m+1,t,rc));
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m,c=0;
    cin>>m;
    build(1,Size,1);
    while(m--){
        int d,x,y;
        cin>>d>>x>>y;
        if(d==1){
            c=query(x+c,y+c,1,Size,1).cnt;
            cout<<c<<"\n";
        }
        else    modify(x+c,y+c,1,Size,1,1);
    }
    return 0;
}
/*
check:
1.read problem statement correctly
2.int overflow
3.array out of bound
4.special case(0 or 1)
5.time complexity
6.try to change dimension in array!!!
*/

• Subtask 1: 0 / 100