Submission #1031437

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1031437	2024-07-22T20:40:39 Z	abdelrahim	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	361 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	0 ms	348 KB	Output is correct
4	Correct	16 ms	8148 KB	Output is correct
5	Correct	21 ms	9856 KB	Output is correct
6	Correct	20 ms	9300 KB	Output is correct
7	Correct	21 ms	9776 KB	Output is correct
8	Correct	169 ms	72784 KB	Output is correct
9	Correct	308 ms	125268 KB	Output is correct
10	Correct	333 ms	139344 KB	Output is correct
11	Correct	357 ms	150356 KB	Output is correct
12	Correct	361 ms	155200 KB	Output is correct
13	Correct	318 ms	185736 KB	Output is correct
14	Correct	309 ms	187988 KB	Output is correct
15	Runtime error	355 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-