oj.uz

Submission #416689

# Submission time Handle Problem Language Result Execution time Memory
416689 2021-06-02T19:15:12 Z MarcoMeijer Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 464 ms 40388 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 23 ms 1252 KB Output is correct
5 Correct 30 ms 1556 KB Output is correct
6 Correct 28 ms 1460 KB Output is correct
7 Correct 30 ms 1476 KB Output is correct
8 Correct 174 ms 10084 KB Output is correct
9 Correct 398 ms 17752 KB Output is correct
10 Correct 385 ms 19652 KB Output is correct
11 Correct 386 ms 20500 KB Output is correct
12 Correct 395 ms 21108 KB Output is correct
13 Correct 355 ms 22184 KB Output is correct
14 Correct 348 ms 22660 KB Output is correct
15 Correct 443 ms 39584 KB Output is correct
16 Correct 464 ms 39680 KB Output is correct
17 Correct 355 ms 23332 KB Output is correct
18 Correct 359 ms 23364 KB Output is correct
19 Correct 441 ms 40324 KB Output is correct
20 Correct 445 ms 40388 KB Output is correct