답안 #475563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475563	2021-09-23T02:45:40 Z	Killer2501	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	136 ms	158028 KB

apple

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const int M = 405;
const ll mod = 1e15+3;
const int base = 400;
ll n, m, k, t, ans, a[N], b[N], dp[N], d[N], tong, c[N], cnt;
map<ll, ll> fe[N];
vector<ll> adj[N];
vector<ll> kq;
ll pw(ll k, ll n)
{
	ll total = 1;
	for(; n; n >>= 1)
	{
		if(n & 1)total = total * k % mod;
		k = k * k % mod;
	}
	return total;
}
struct node
{
	ll l, r, val;
	node()
	{
		l = r = val;
	}
}st[N*30];
string s;
void update(ll id, ll l, ll r, ll u, ll v)
{
	if(st[id].val == r-l+1)return;
	if(u <= l && r <= v)
	{
		st[id].val = r-l+1;
		return;
	}
	ll mid = (l+r)/2;
	if(u <= mid)
	{
		if(!st[id].l )st[id].l = ++cnt;
		update(st[id].l, l, mid, u, v);
	}
	if(mid+1 <= v)
	{
		if(!st[id].r)st[id].r = ++cnt;
		update(st[id].r, mid+1, r, u, v);
	}
	st[id].val = st[st[id].l].val + st[st[id].r].val;
}
ll get(ll id, ll l, ll r, ll u, ll v)
{
	if(!id)return 0;
	if(u <= l && r <= v)return st[id].val;
    if(st[id].val == r-l+1)return min(v, r) - max(u, l) + 1;
    ll mid = (l+r)/2;
    ll total = 0;
    if(u <= mid)total += get(st[id].l, l, mid, u, v);
    if(mid+1 <= v)total += get(st[id].r, mid+1, r, u, v);
    return total;
}
void sol()
{
	cin >> m;
	n = 1e9;
	ll x, y;
	cnt = 1;
	while(m -- > 0)
	{
		cin >> t >> x >> y;
		x += ans;
		y += ans;
		if(t == 2)update(1, 1, n, x, y);
		else cout << (ans = get(1, 1, n, x, y)) << '\n';
	}

}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}
/*
6 7
1 2
1 3
2 4
4 6
2 5
1 4
2 2 4
1 1
2 2 2
1 2
1 5
2 2 2
*/

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:94:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:95:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp: In constructor 'node::node()':
apple.cpp:34:11: warning: '*<unknown>.node::val' is used uninitialized in this function [-Wuninitialized]
   34 |   l = r = val;
      |           ^~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	155332 KB	Output is correct
2	Correct	91 ms	155288 KB	Output is correct
3	Correct	88 ms	155296 KB	Output is correct
4	Correct	91 ms	155364 KB	Output is correct
5	Correct	96 ms	155416 KB	Output is correct
6	Correct	96 ms	155464 KB	Output is correct
7	Correct	89 ms	155432 KB	Output is correct
8	Correct	112 ms	156356 KB	Output is correct
9	Correct	126 ms	157336 KB	Output is correct
10	Correct	128 ms	157428 KB	Output is correct
11	Correct	125 ms	157372 KB	Output is correct
12	Correct	123 ms	157456 KB	Output is correct
13	Correct	136 ms	157864 KB	Output is correct
14	Correct	132 ms	157800 KB	Output is correct
15	Correct	122 ms	157892 KB	Output is correct
16	Correct	124 ms	157936 KB	Output is correct
17	Correct	120 ms	157752 KB	Output is correct
18	Correct	119 ms	157760 KB	Output is correct
19	Correct	130 ms	158028 KB	Output is correct
20	Correct	125 ms	157908 KB	Output is correct