oj.uz

Submission #1081357

# Submission time Handle Problem Language Result Execution time Memory
1081357 2024-08-30T01:14:20 Z The_Eureka Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 249 ms 152428 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);
}


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 (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 63 ms 150688 KB Output is correct
2 Correct 60 ms 150680 KB Output is correct
3 Correct 61 ms 150612 KB Output is correct
4 Correct 68 ms 150656 KB Output is correct
5 Correct 69 ms 150828 KB Output is correct
6 Correct 71 ms 150868 KB Output is correct
7 Correct 68 ms 150868 KB Output is correct
8 Correct 120 ms 151636 KB Output is correct
9 Correct 212 ms 151884 KB Output is correct
10 Correct 199 ms 151892 KB Output is correct
11 Correct 210 ms 152128 KB Output is correct
12 Correct 207 ms 151888 KB Output is correct
13 Correct 224 ms 152296 KB Output is correct
14 Correct 196 ms 152384 KB Output is correct
15 Correct 245 ms 152312 KB Output is correct
16 Correct 243 ms 152400 KB Output is correct
17 Correct 193 ms 152340 KB Output is correct
18 Correct 201 ms 152344 KB Output is correct
19 Correct 237 ms 152428 KB Output is correct
20 Correct 249 ms 152400 KB Output is correct