Submission #501959

#	Time	Username	Problem	Language	Result	Execution time	Memory
501959		BeanZ	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	425 ms	262144 KiB

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

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