Submission #501959

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
501959	2022-01-04T23:39:52 Z	BeanZ	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	425 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const int N = 1e7 + 5;
const long long mod = 1e9 + 7;
const int mod2 = 998244353;
const long long lim = 1e9;
const int lg = 22;
const int base = 311;
const int base2 = 511;
const long double eps = 1e-12;
ll st[N], lazy[N], L[N], R[N];
ll cnt = 1;
void down(ll k, ll l, ll r){
    if (L[k] == 0) cnt++, L[k] = cnt;
    if (R[k] == 0) cnt++, R[k] = cnt;
    ll mid = (l + r) >> 1;
    st[L[k]] = mid - l + 1;
    st[R[k]] = r - mid;
    lazy[L[k]] = 1;
    lazy[R[k]] = 1;
    lazy[k] = 0;
}
ll get(ll k, ll l, ll r, ll x, ll y){
    if (l != r && lazy[k]) down(k, l, r);
    if (x > r || y < l) return 0;
    if (x <= l && y >= r) return st[k];
    ll res = 0;
    ll mid = (l + r) >> 1;
    if (L[k]) res = res + get(L[k], l, mid, x, y);
    if (R[k]) res = res + get(R[k], mid + 1, r, x, y);
    //cout << l << " " << r << " " << res << endl;
    return res;
}
void upd(ll k, ll l, ll r, ll x, ll y){
    if (l != r && lazy[k]) down(k, l, r);
    if (x > r || y < l) return;
    if (x <= l && y >= r){
        st[k] = r - l + 1;
        lazy[k] = 1;
        return;
    }
    ll mid = (l + r) >> 1;
    if (L[k] == 0) cnt++, L[k] = cnt;
    if (R[k] == 0) cnt++, R[k] = cnt;
    upd(L[k], l, mid, x, y);
    upd(R[k], mid + 1, r, x, y);
    st[k] = st[L[k]] + st[R[k]];
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("tests.inp", "r", stdin);
        freopen("tests.out", "w", stdout);
    }
    ll m;
    cin >> m;
    ll c = 0;
    while (m--){
        ll d, x, y;
        cin >> d >> x >> y;
        x += c;
        y += c;
        if (d == 1){
            c = get(1, 1, lim, x, y);
            cout << c << endl;
        } else {
            upd(1, 1, lim, x, y);
        }
    }
}
/*
Ans:

Out:
*/

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen("tests.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen("tests.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	11 ms	5796 KB	Output is correct
5	Correct	16 ms	7024 KB	Output is correct
6	Correct	16 ms	6732 KB	Output is correct
7	Correct	14 ms	7000 KB	Output is correct
8	Correct	136 ms	51412 KB	Output is correct
9	Correct	301 ms	87424 KB	Output is correct
10	Correct	274 ms	98096 KB	Output is correct
11	Correct	304 ms	108244 KB	Output is correct
12	Correct	297 ms	111928 KB	Output is correct
13	Correct	246 ms	138948 KB	Output is correct
14	Correct	254 ms	140340 KB	Output is correct
15	Correct	407 ms	254592 KB	Output is correct
16	Correct	415 ms	256560 KB	Output is correct
17	Correct	268 ms	145488 KB	Output is correct
18	Correct	263 ms	145460 KB	Output is correct
19	Correct	411 ms	262144 KB	Output is correct
20	Correct	425 ms	262144 KB	Output is correct