oj.uz

Submission #1081356

# Submission time Handle Problem Language Result Execution time Memory
1081356 2024-08-30T01:13:07 Z The_Eureka Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 296 ms 153432 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define alls(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define rep(i, n) for (int i = 1; i <= int(n); i++)
#define inc(i, l, r, d) for (int i = l; i <= r; i += d)
#define dec(i, r, l, d) for (int i = r; i >= l; i -= d) 
#define dbg(x) cerr << #x << " = " << x << endl;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
const ld eps = 1e-12;
const ll inf = 1e16;
const ll mod = 998244353;
const ll mod1 = 1e9 + 87;
const ll mod2 = 127397154761;
ll qpow(ll a, ll b) {if (b == 0) return 1; ll ans = qpow(a, b >> 1); ans = ans * ans % mod; if (b & 1) ans = ans * a % mod; return ans;}
using namespace std;

void IOS(string name = "") {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    if ((int)name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

#define mid (info[rt].tl + info[rt].tr) / 2


struct node {
    int sum, tr, tl, l, r, lazy;

    node(): sum(0), tr(0), tl(0), l(-1), r(-1), lazy(0) {}
};
const int maxn = 6400000;
node info[maxn];
int cnt = 1;

void extend_left(int rt) {
    if (info[rt].l == -1) {
        info[rt].l = ++cnt;
        info[cnt].tl = info[rt].tl;
        info[cnt].tr = mid;
    }
}

void extend_right(int rt) {
    if (info[rt].r == -1) {
        info[rt].r = ++cnt;
        info[cnt].tl = mid + 1;
        info[cnt].tr = info[rt].tr;
    }
}

void put_tag(int rt) {
    info[rt].sum = info[rt].tr - info[rt].tl + 1;
    info[rt].lazy = 1;
}

void push_down(int rt) {
    if (info[rt].tl == info[rt].tr) return;
    if (info[rt].l == -1) {
        extend_left(rt);
    }
    if (info[rt].r == -1) {
        extend_right(rt);
    }
    if (info[rt].lazy) {
        put_tag(info[rt].l);
        put_tag(info[rt].r);
        info[rt].lazy = 0;
    }
}

void push_up(int rt) {
    info[rt].sum = info[info[rt].l].sum + info[info[rt].r].sum;
}

void update(int rt, int L, int R) {
    push_down(rt);
    if (info[rt].tl >= L && info[rt].tr <= R) {
        put_tag(rt);
        return;
    }
    if (L <= mid) {
        if (info[rt].l == -1) {
            extend_left(rt);
        }
        update(info[rt].l, L, R);
    }
    if (R > mid) {
        if (info[rt].r == -1) {
            extend_right(rt);
        }
        update(info[rt].r, L, R);
    }
    push_up(rt);
    //dbg(info[rt].tl);
    //dbg(info[rt].tr);
    //dbg(info[rt].sum);
}

int times = 0;

int qry(int rt, int L, int R) {
    push_down(rt);
    if (L <= info[rt].tl && info[rt].tr <= R) {
        return info[rt].sum;
    }
    int ans = 0;
    if (info[rt].tl == 0 && info[rt].tr == 0) {
        times++;
        if (times > 10) {
            return 0;
        }
    }
    if (L <= mid) {
        ans += qry(info[rt].l, L, R);
    }
    if (R > mid) {
        ans += qry(info[rt].r, L, R);
    }
    return ans;
}

int main() {
    IOS();
    info[1].tl = 1, info[1].tr = 1e9;
    int m; cin >> m;
    int C = 0;
    rep(ii, m) {
        int ins, l, r;
        cin >> ins >> l >> r;
        if (ins == 2) {
            update(1, l + C, r + C);
        }
        else {
            C = qry(1, l + C, r + C);
            cout << C << '\n';
        }
        ///dbg(qry(1, 1, 1000000000))
    }
    return 0;
}

Compilation message

apple.cpp: In function 'void IOS(std::string)':
apple.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 150608 KB Output is correct
2 Correct 61 ms 150608 KB Output is correct
3 Correct 61 ms 150608 KB Output is correct
4 Correct 68 ms 150740 KB Output is correct
5 Correct 66 ms 150612 KB Output is correct
6 Correct 70 ms 150756 KB Output is correct
7 Correct 70 ms 150612 KB Output is correct
8 Correct 120 ms 150740 KB Output is correct
9 Correct 221 ms 150868 KB Output is correct
10 Correct 194 ms 150864 KB Output is correct
11 Correct 208 ms 151108 KB Output is correct
12 Correct 203 ms 150868 KB Output is correct
13 Correct 194 ms 150988 KB Output is correct
14 Correct 205 ms 151216 KB Output is correct
15 Correct 238 ms 151020 KB Output is correct
16 Correct 296 ms 153372 KB Output is correct
17 Correct 222 ms 153168 KB Output is correct
18 Correct 210 ms 153120 KB Output is correct
19 Correct 247 ms 153432 KB Output is correct
20 Correct 247 ms 153168 KB Output is correct