답안 #556311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556311	2022-05-02T20:40:03 Z	SharpEdged	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	566 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() {};
	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){
	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;
	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

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	85 ms	185804 KB	Output is correct
2	Correct	82 ms	185844 KB	Output is correct
3	Correct	82 ms	185848 KB	Output is correct
4	Correct	91 ms	185992 KB	Output is correct
5	Correct	114 ms	185932 KB	Output is correct
6	Correct	120 ms	185960 KB	Output is correct
7	Correct	100 ms	185972 KB	Output is correct
8	Correct	190 ms	186328 KB	Output is correct
9	Correct	330 ms	186840 KB	Output is correct
10	Correct	350 ms	186776 KB	Output is correct
11	Correct	340 ms	186724 KB	Output is correct
12	Correct	380 ms	186780 KB	Output is correct
13	Correct	323 ms	186540 KB	Output is correct
14	Correct	317 ms	186524 KB	Output is correct
15	Runtime error	566 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-