oj.uz

Submission #1030549

# Submission time Handle Problem Language Result Execution time Memory
1030549 2024-07-22T06:44:16 Z Gray Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 393 ms 262144 KB 
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <ios>
#include <iostream>
#include <map>
#include <ratio>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define ull unsigned long long int
#define ld double
#define ln "\n"
#define ff first
#define ss second
using namespace std;

const ll inf=2e18;

void setio(string io=""){
	#ifndef LOCAL
	if (io.length()){
		freopen((io+".in").c_str(), "r", stdin);
		freopen((io+".out").c_str(), "w", stdout);
		return;
	}
	#endif
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
}

struct Node{
	map<ll, Node*> child;
	ll val, lazy;
	Node(){
		val=0; lazy=-1;
	}
	void preprocess(ll tl, ll tr){
		if (lazy!=-1){
			val=tr-tl+1;
			lazy=-1;
			if (!child.count(0)) child[0]=new Node;
			child[0]->lazy=1;
			if (!child.count(1)) child[1]=new Node;
			child[1]->lazy=1;
		}
	}
	void update(ll tl, ll tr, ll l, ll r){
		preprocess(tl, tr);
		if (tl==l and tr==r){
			lazy=1;
			preprocess(tl, tr);			
		}else if (l>r) return;
		else{
			ll tm = (tl+tr)/2;
			if (!child.count(0)) child[0]=new Node;
			child[0]->update(tl, tm, l, min(r, tm));
			if (!child.count(1)) child[1]=new Node;
			child[1]->update(tm+1, tr, max(tm+1, l), r);
			val=child[0]->val+child[1]->val;
		}
	}
	ll query(ll l, ll r, ll tl, ll tr){
		preprocess(tl, tr);
		if (l==tl and r==tr){
			return val;
		}else if (l>r) return 0;
		else{
			ll tm = (tl+tr)/2;
			ll ans=0;
			if (child.count(0)) ans+=child[0]->query(l, min(r, tm), tl, tm);
			if (child.count(1)) ans+=child[1]->query(max(l, tm+1), r, tm+1, tr);
			return ans;
		}
	}
};

void solve(){
	Node tr;
	ll l=1, r=1e9;
	ll q; cin >> q;
	ll c=0;
	while (q--){
		ll t, x, y; cin >> t >> x >> y;
		if (t==1){
			c = tr.query(x+c, y+c, l, r);
			cout << c << ln;
		}else{
			tr.update(l, r, x+c, y+c);
		}
	}
}

int main(){
	setio();
	ll t=1;
	// cin >> t;
	while (t--) solve();
}

Compilation message

apple.cpp: In function 'void setio(std::string)':
apple.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen((io+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   freopen((io+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 35 ms 27660 KB Output is correct
5 Correct 43 ms 33748 KB Output is correct
6 Correct 42 ms 32604 KB Output is correct
7 Correct 43 ms 33616 KB Output is correct
8 Correct 393 ms 260688 KB Output is correct
9 Runtime error 367 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -