oj.uz

Submission #1081354

# Submission time Handle Problem Language Result Execution time Memory
1081354 2024-08-30T01:11:04 Z The_Eureka Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 258 ms 193620 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 = 4000000;
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) {
    if (info[rt].tl >= L && info[rt].tr <= R) {
        put_tag(rt);
        return;
    }
    push_down(rt);
    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) {
    if (L <= info[rt].tl && info[rt].tr <= R) {
        return info[rt].sum;
    }
    int ans = 0;
    push_down(rt);
    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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94292 KB Output is correct
2 Correct 39 ms 94288 KB Output is correct
3 Correct 48 ms 94288 KB Output is correct
4 Correct 53 ms 94288 KB Output is correct
5 Correct 49 ms 94380 KB Output is correct
6 Correct 47 ms 94560 KB Output is correct
7 Correct 51 ms 94544 KB Output is correct
8 Correct 96 ms 95316 KB Output is correct
9 Correct 152 ms 96424 KB Output is correct
10 Correct 166 ms 96384 KB Output is correct
11 Correct 163 ms 96340 KB Output is correct
12 Correct 170 ms 96336 KB Output is correct
13 Correct 179 ms 96896 KB Output is correct
14 Correct 154 ms 96852 KB Output is correct
15 Runtime error 258 ms 193620 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -