Submission #416689

#	Time	Username	Problem	Language	Result	Execution time	Memory
416689		MarcoMeijer	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	464 ms	40388 KiB

apple

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second

const int INF	= 1<<30;
const int MX	= 5e5;
const int N	= 1<<23;
const int MOD	= 1e9+7;

int n;
int seg[N], pl[N], pr[N], laz[N];
int segcnt=1;

void createChildren(int p) {
  if(pl[p]) return;
  pl[p] = segcnt++;
  pr[p] = segcnt++;
}
void setSeg(int i, int j, int lazy=0, int p=0, int l=0, int r=INF-1) {
  if(lazy) {
    seg[p] = r-l+1;
    laz[p] = 1;
  }
  if(j < l || i > r) return;
  if(i <= l && j >= r) {
    seg[p] = r-l+1;
    laz[p] = 1;
    return;
  }
  int m=(l+r)/2;
  createChildren(p);
  setSeg(i,j,laz[p],pl[p],l,m);
  setSeg(i,j,laz[p],pr[p],m+1,r);
  laz[p] = 0;
  seg[p] = seg[pl[p]]+seg[pr[p]];
}
int getSeg(int i, int j, int lazy=0, int p=0, int l=0, int r=INF-1) {
  if(lazy) {
    seg[p] = r-l+1;
    laz[p] = 1;
  }
  if(j < l || i > r) return 0;
  if(i <= l && j >= r) return seg[p];
  int m=(l+r)/2;
  if(pl[p]==0) return laz[p] ? min(j,r)-max(i,l)+1 : 0;
  int a=getSeg(i,j,laz[p],pl[p],l,m);
  int b=getSeg(i,j,laz[p],pr[p],m+1,r);
  laz[p] = 0;
  return a+b;
}

int main() {
  cin>>n;
  int c=0;
  RE(i,n) {
    int q, x, y;
    cin>>q>>x>>y;
    x+=c; y+=c;
    if(q == 1) {
      c = getSeg(x,y);
      cout<<c<<endl;
    }
    if(q == 2) {
      setSeg(x,y);
    }
  }
}

• Subtask 1: 100 / 100