Submission #491277

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
491277	2021-12-01T09:47:54 Z	Karliver	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	40 ms	2980 KB

apple

	
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()

using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}
const int SZ = 1e9 + 1;
struct segment{
	int x;
	segment *link[2];
	void update(int s,int d,int l,int r)
	{
		if(x == d-s+1)return;
		if(l<=s && d<=r){
			x = d-s+1;
			return;
		}
		int m = (s+d)>>1;
		if(l<=m){
			if(!link[0])link[0] = new segment();
			link[0]->update(s,m,l,r);
		}
		if(r>m){
			if(!link[1])link[1] = new segment();
			link[1]->update(m+1,d,l,r);
		}
		x = (link[0]?link[0]->x:0) + (link[1]?link[1]->x:0);
	}
	int read(int s,int d,int l,int r)
	{
		if(l<=s && d<=r)return x;
		if(x == d-s+1)return std::min(d,r) - std::max(s,l) + 1;
		int m = (s+d)>>1, ret = 0;
		if(l<=m)ret += link[0]?link[0]->read(s,m,l,r):0;
		if(r>m)ret += link[1]?link[1]->read(m+1,d,l,r):0;
		return ret;
	}
}S;
void solve() {


	int Q;
	cin >> Q;
	int pr = 0;
	
	while(Q--) {
		int t, x, y;
		cin >> t >> x >> y;
		x += pr;
		y += pr;
		if(t == 1) {	
			int ret = S.read(1, 1e9, x, y);
			cout << ret << '\n';
			swap(ret, pr);
		}
		else {
			S.update(1, 1e9, x, y);
		}
	}


}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	4 ms	460 KB	Output is correct
5	Correct	4 ms	460 KB	Output is correct
6	Correct	4 ms	460 KB	Output is correct
7	Correct	4 ms	452 KB	Output is correct
8	Correct	17 ms	1356 KB	Output is correct
9	Correct	34 ms	2412 KB	Output is correct
10	Correct	33 ms	2364 KB	Output is correct
11	Correct	30 ms	2460 KB	Output is correct
12	Correct	30 ms	2408 KB	Output is correct
13	Correct	35 ms	2852 KB	Output is correct
14	Correct	40 ms	2892 KB	Output is correct
15	Correct	31 ms	2916 KB	Output is correct
16	Correct	33 ms	2884 KB	Output is correct
17	Correct	29 ms	2872 KB	Output is correct
18	Correct	30 ms	2800 KB	Output is correct
19	Correct	31 ms	2912 KB	Output is correct
20	Correct	31 ms	2980 KB	Output is correct