제출 #1031437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031437		abdelrahim	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	361 ms	262144 KiB

apple

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <complex>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#include <chrono>

using namespace std;
using namespace std::chrono;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;

typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef set<int> si;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less

#define all(a) (a).begin(), (a).end()
#define pb              push_back
#define fi              first
#define sc              second
using namespace __gnu_pbds;
using namespace std;



template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef tree<pair<int, int>, null_type,
        greater<pair<int, int>>, rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_multiset;
// ll mod = 1000000007;
const double pi = acos(-1);

int n, m, k;
string s;

void yes()
{
    cout << "Yes" << endl;
}
void no()
{
    cout << "No" << endl;
}


struct node {
  int from, to;
  long long value, lazy;
  node *left, *right;
  node() {
    from=1;
    to=1e9;
    value=0;
    lazy=0;
    left=NULL;
    right=NULL;
  }
  void extend() {
    if(left==NULL) {
      left=new node();
      right=new node();
      left->from=from;
      left->to=(from+to)>>1;
      right->from=((from+to)>>1)+1;
      right->to=to;
    }
  }
};

node *root;

void update_tree(node *curr, int left, int right, long long value) {
  if(curr->lazy) {
    curr->value = (curr->to-curr->from+1);
    if(curr->from!=curr->to) {
      curr->extend();
      curr->left->lazy+=curr->lazy;
      curr->right->lazy+=curr->lazy;
    }
    curr->lazy=0;
  }
  if((curr->from)>(curr->to) || (curr->from)>right || (curr->to)<left) return;
  if(curr->from>=left && curr->to<=right) {
    curr->value = (curr->to-curr->from+1);
    if(curr->from!=curr->to) {
      curr->extend();
      curr->left->lazy+=value;
      curr->right->lazy+=value;
    }
    return;
  }
  curr->extend();
  update_tree(curr->left,left,right,value);
  update_tree(curr->right,left,right,value);
  curr->value= curr->left->value + curr->right->value;
}

long long query_tree(node *curr, int left, int right) {
  if((curr->from)>(curr->to) || (curr->from)>right || (curr->to)<left) return 0;
  if(curr->lazy) {
    curr->value = (curr->to-curr->from+1);
    curr->extend();
    curr->left->lazy+=curr->lazy;
    curr->right->lazy+=curr->lazy;
    curr->lazy=0;
  }
  if(curr->from>=left && curr->to<=right) return curr->value;
  long long q1,q2;
  curr->extend();
  q1=query_tree(curr->left,left,right);
  q2=query_tree(curr->right,left,right);
  return q1+q2;
}

void solve(){
    root = new node();
    cin>>n;
    int c = 0;
    int t,l,r;
    while(n--){
        cin>> t>>l>>r;
        if(t==1){
             c = query_tree(root,l+ c,r+c);
            cout<< c<<endl;
        }
        else{
            update_tree(root,l+c,r+c,1);
        }
    }


}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t =1;
    //cin>>t;
    while(t--)
    solve();
    return 0;
}

• Subtask 1: 0 / 100