Submission #300087

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
300087	2020-09-16T14:36:04 Z	NaimSS	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	375 ms	167032 KB

apple

#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) (int)v.size()
//#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; 
#define prl cerr<<"called: "<< __LINE__ << endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}

const int MX = 1e9 + 7;

struct node{
  node *l,*r;
  int L,R;
  bool lazy;
  int sum;
  node(){}
  node(int A,int B){
    l = r = NULL;
    L = A,R = B;
    sum = 0;
    lazy = 0;
  }
  void flush(){
    if(!lazy)return;
    lazy=0;
    sum = R - L + 1;
    int mid = (L+R)/2;
    if(L!=R){
      if(!l)l = new node(L,mid);
      if(!r)r = new node(mid+1,R);
      l->lazy = r->lazy = 1;
    }
  }
  int Sum(node * no){
    if(!no)return 0;
    return no->sum;
  }
  void upd(int a,int b){
    flush();
    if(sum == R - L + 1)return;
    if(a<=L and R<=b){
      lazy = 1;
      flush();
      return;
    }
    int mid = (L+R)/2;
    if(a<=mid){
      if(!l)l = new node(L,mid);
      l->upd(a,min(mid,b));
    }
    if(b>mid){
      if(!r)r = new node(mid+1,R);
      r->upd(max(a,mid+1),b);
    }

    if(l)l->flush();
    if(r)r->flush();
    sum = Sum(l) + Sum(r);
  }
  int query(int a,int b){
    flush();
    if(a<=L and R<=b){
      return sum;
    }
    int mid = (L+R)/2;
    int op1=0,op2=0;
    if(a<=mid and l)op1 = l->query(a,b);
    if(b>mid and r)op2 = r->query(a,b);
    return op1 + op2;
  }
};

int32_t main(){
  fastio;
  int m;
  cin >> m;
  node* tree = new node(1,MX);
  int C=0;
  while(m--){
    int D,X,Y;
    cin >> D >> X >> Y;
    X+=C,Y+=C;
    if(D == 1){
      cout << (C = tree->query(X,Y)) << endl;
    }else{
      tree->upd(X,Y);
    }
  }
  
  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	12 ms	4352 KB	Output is correct
5	Correct	13 ms	5248 KB	Output is correct
6	Correct	15 ms	4992 KB	Output is correct
7	Correct	13 ms	5248 KB	Output is correct
8	Correct	118 ms	38520 KB	Output is correct
9	Correct	197 ms	67192 KB	Output is correct
10	Correct	225 ms	73592 KB	Output is correct
11	Correct	244 ms	78456 KB	Output is correct
12	Correct	256 ms	80504 KB	Output is correct
13	Correct	249 ms	88952 KB	Output is correct
14	Correct	246 ms	88568 KB	Output is correct
15	Correct	375 ms	161656 KB	Output is correct
16	Correct	343 ms	163448 KB	Output is correct
17	Correct	227 ms	91256 KB	Output is correct
18	Correct	212 ms	91460 KB	Output is correct
19	Correct	333 ms	166776 KB	Output is correct
20	Correct	330 ms	167032 KB	Output is correct