답안 #556308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556308	2022-05-02T20:37:07 Z	SharpEdged	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	595 ms	262144 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(int _lx, int _rx){
		lx = _lx; rx = _rx;
	}
};

vector<Node> st = {Node(0, 1e9+5)};
int cnt = 1;

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

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

void prop(int x){
	makeChild(x);
	if (!st[x].lzy) return;
	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 (st[x].rx < l || r < st[x].lx) return;
	if (l <= st[x].lx && st[x].rx <= r){
		app(x);
		return;
	}
	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 (st[x].rx < l || r < st[x].lx) return 0;
	if (l <= st[x].lx && st[x].rx <= r) return st[x].val;
	return qry(st[x].c[0], l, r) + qry(st[x].c[1], l, r);
}

void TestCase(){
	int m;
	cin >> m;
	int c = 0;
	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

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	20 ms	6716 KB	Output is correct
5	Correct	26 ms	6724 KB	Output is correct
6	Correct	25 ms	6744 KB	Output is correct
7	Correct	25 ms	6724 KB	Output is correct
8	Correct	177 ms	50308 KB	Output is correct
9	Correct	364 ms	100064 KB	Output is correct
10	Correct	375 ms	99708 KB	Output is correct
11	Correct	378 ms	99664 KB	Output is correct
12	Correct	392 ms	99548 KB	Output is correct
13	Correct	430 ms	198604 KB	Output is correct
14	Correct	417 ms	198948 KB	Output is correct
15	Runtime error	595 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-