Submission #524638

#	Time	Username	Problem	Language	Result	Execution time	Memory
524638		Pety	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	0 ms	204 KiB

apple

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;

int n;

struct aint {
  int sum, lazy;
  aint *st, *dr;
  aint() {
    st = dr = NULL;
    lazy = -1;
    sum = 0;
  }
}*root;

void push (aint* node, int st, int dr) {
  if (node->lazy == -1)
    return;
  node->sum = (dr - st + 1) * node->lazy;
  if (st != dr) {
    if (node->st != NULL)
      node->st->lazy = node->lazy;
    if (node->dr != NULL)
      node->dr->lazy = node->lazy;
  }
  node->lazy = -1;
} 

void update (aint* root, int st, int dr, int a, int b) {
  if (root->st == NULL) root->st = new aint;
  if (root->dr == NULL) root->dr = new aint;
  push(root, st, dr);
  if (st > dr || b < st || a > dr)
    return;
  if (a <= st && dr <= b) {
    root->sum = dr - st + 1;
    if (st != dr) {
      root->st->lazy = 1;
      root->st->lazy = 1;
    }
    return;
  }
  int mij = (st + dr) / 2;
  update(root->st, st, mij, a, b);
  update(root->dr, mij + 1, dr, a, b);
  root->sum = root->st->sum + root->dr->sum;
}

int query (aint* root, int st, int dr, int a, int b) {
  if (root == NULL)
    return 0;
  push(root, st, dr);
  if (st > dr || b < st || a > dr)
    return 0;
  if (a <= st && dr <= b) 
    return root->sum;
  int mij = (st + dr) / 2;
  return (query(root->st, st, mij, a, b) + query(root->dr, mij + 1, dr, a, b));
}



int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  root = new aint;
  int c = 0;
  for (int i = 1; i <= n; i++) {
    int d, x, y;
    cin >>d >> x >> y;
    x += c; y += c; 
    if (d == 1) {
      c = query(root, 1, INF, x, y);
      cout << c << "\n";
    }
    else {
      update(root, 1, INF, x, y);
    }
  }
  
  
  return 0;
}

• Subtask 1: 0 / 100