Submission #1031433

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1031433	2024-07-22T20:36:13 Z	abdelrahim	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	372 ms	262144 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	17 ms	7940 KB	Output is correct
5	Correct	19 ms	9816 KB	Output is correct
6	Correct	19 ms	9304 KB	Output is correct
7	Correct	20 ms	9660 KB	Output is correct
8	Correct	150 ms	72652 KB	Output is correct
9	Correct	306 ms	125264 KB	Output is correct
10	Correct	344 ms	139432 KB	Output is correct
11	Correct	319 ms	150356 KB	Output is correct
12	Correct	331 ms	155272 KB	Output is correct
13	Correct	302 ms	185868 KB	Output is correct
14	Correct	314 ms	188128 KB	Output is correct
15	Runtime error	372 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-