Submission #475563

#	Time	Username	Problem	Language	Result	Execution time	Memory
475563		Killer2501	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	136 ms	158028 KiB

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 (stderr)

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 / 100