답안 #556316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556316	2022-05-02T20:53:17 Z	SharpEdged	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	399 ms	188552 KB

apple

#include <bits/stdc++.h>
 
using namespace std;
 
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define LSB(x) ((x) & -(x))
#define sz(x) (int)(x.size())
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define __lcm(a, b) ((a) * (b)) / __gcd(a, b)
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[DEBUG] "<<__func__<<": "<<__LINE__<<", [" << #x << "] = ["; _print(x);
#else
#define dbg(x...)
#endif
 
 
struct Data {
	int r1, c1, r2, c2, d;
	Data(int _r1, int _c1, int _r2, int _c2, int _d) : r1(_r1), c1(_c1), r2(_r2), c2(_c2), d(_d) {};
	bool operator== (const Data& b) const {
		return r1 == b.r1 && r2 == b.r2 && c1 == b.c1 && c2 == b.c2 && d == b.d;
	}
};
 
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
    
    size_t operator()(string x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        uint64_t res = 0;
        for (int i = 0; i < sz(x); i++){
			res ^= x[i] + FIXED_RANDOM;
			res = splitmix64(res);
		}
        return res;
    }
    
    size_t operator()(Data x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		uint64_t res = ((splitmix64(x.r1) ^ splitmix64(splitmix64(x.c1) + FIXED_RANDOM)) ^ splitmix64(splitmix64(x.r2) ^ (splitmix64(splitmix64(x.c2)) ^ x.d))) + FIXED_RANDOM;
		return res;
	}
};
 
const ll MOD = 1e9 + 7;
const ll INFLL = 1e18 + 5;
const int INF = 1e9 + 5;
 
char nl = '\n';
 
ll modPow(ll n, ll k){
	if (k == 0) return 1;
	ll res = modPow(n, k / 2);
	res = res * res % MOD;
	if (k & 1) return res * n % MOD;
	return res;
}
 
 
const int mxN = 1e5;
 
bool ccw(pair<ll, ll> p1, pair<ll, ll> p2, pair<ll, ll> p3){
	ll val = (p1.f * p2.s - p1.s * p2.f + p2.f * p3.s - p2.s * p3.f + p3.f * p1.s - p3.s * p1.f);
	if  (val <= 0) return 1;
	return 0;
}
 
const int MAXN = 50005;
const int MAXK = 505;

struct Node{
	int val = 0, lx = 0, rx = 0, lzy = 0;
	int c[2] = {-1, -1};
	Node() {};
	Node(int _lx, int _rx){
		lx = _lx; rx = _rx;
	}
};

Node st[64*123456];
int cnt = 1;

void makeChild(int x){
	int mid = (st[x].lx + st[x].rx) / 2;
	if (st[x].c[0] == -1) { st[cnt] = Node(st[x].lx, mid); st[x].c[0] = cnt++; } 
	if (st[x].c[1] == -1) { st[cnt] = Node(mid+1, st[x].rx); st[x].c[1] = cnt++; }
}

void app(int x){
	st[x].lzy = 1;
	st[x].val = st[x].rx - st[x].lx + 1;
}

void prop(int x){
	if (!st[x].lzy) return;
	makeChild(x);
	app(st[x].c[0]);
	app(st[x].c[1]);
	st[x].lzy = 0;
}

void upd(int x, int l, int r){
	prop(x);
	if (l <= st[x].lx && st[x].rx <= r){
		app(x);
		return;
	}
	makeChild(x);
	int mid = (st[x].lx + st[x].rx) / 2;
	if (l > mid) upd(st[x].c[1], l, r);
	else if (r <= mid) upd(st[x].c[0], l, r);
	else {
		upd(st[x].c[0], l, r);
		upd(st[x].c[1], l, r);
	}
	st[x].val = st[st[x].c[0]].val + st[st[x].c[1]].val;
}

int qry(int x, int l, int r){
	prop(x);
	if (l <= st[x].lx && st[x].rx <= r) return st[x].val;
	makeChild(x);
	int mid = (st[x].lx + st[x].rx) / 2;
	if (l > mid) return qry(st[x].c[1], l, r);
	else if (r <= mid) return qry(st[x].c[0], l, r);
	else return qry(st[x].c[0], l, r) + qry(st[x].c[1], l, r);
}

void TestCase(){
	int m;
	cin >> m;
	int c = 0;
	st[0] = Node(0, 1e9+5);
	while (m--){
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 1){
			c = qry(0, x+c, y+c);
			cout << c << nl;
		} else {
			upd(0, x+c, y+c);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int T = 1;
	//cin >> T;
	while (T--){
		TestCase();
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	185764 KB	Output is correct
2	Correct	82 ms	185788 KB	Output is correct
3	Correct	92 ms	185808 KB	Output is correct
4	Correct	96 ms	185848 KB	Output is correct
5	Correct	104 ms	185772 KB	Output is correct
6	Correct	94 ms	185804 KB	Output is correct
7	Correct	104 ms	185860 KB	Output is correct
8	Correct	213 ms	186040 KB	Output is correct
9	Correct	284 ms	186200 KB	Output is correct
10	Correct	312 ms	186168 KB	Output is correct
11	Correct	325 ms	186140 KB	Output is correct
12	Correct	329 ms	186288 KB	Output is correct
13	Correct	283 ms	186452 KB	Output is correct
14	Correct	282 ms	186276 KB	Output is correct
15	Correct	395 ms	188476 KB	Output is correct
16	Correct	362 ms	188428 KB	Output is correct
17	Correct	314 ms	188452 KB	Output is correct
18	Correct	284 ms	188408 KB	Output is correct
19	Correct	399 ms	188436 KB	Output is correct
20	Correct	367 ms	188552 KB	Output is correct