Submission #593885

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
593885	2022-07-11T17:15:51 Z	Do_you_copy	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	334 ms	203348 KB

apple

#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const ll maxN = 1e5 + 1;

ll n;
ll node_cnt = 1;
struct TNode{
    ll l, r, lazy, sum;
    TNode(): l(-1), r(-1), lazy(0), sum(0){}
};
TNode st[maxN * 64];

void add_node(ll id){
    if (st[id].l == -1){
        st[id].l = ++node_cnt;
    }
    if (st[id].r == -1){
        st[id].r = ++node_cnt;
    }
}

void pull(ll id, ll l, ll r){
    if (st[id].lazy){
        ll mid = (l + r) / 2;
        st[st[id].l].lazy = st[id].lazy;
        st[st[id].r].lazy = st[id].lazy;
        st[st[id].l].sum = (mid - l + 1) * st[id].lazy;
        st[st[id].r].sum = (r - mid) * st[id].lazy;
        st[id].lazy = 0;
    }
}

void update(ll id, ll i, ll j, ll x, ll l = 1, ll r = ll(1e9)){
    if (r < i || l > j) return;
    if (i <= l && r <= j){
        st[id].lazy = x;
        st[id].sum = (r - l + 1) * x;
        return;
    }
    add_node(id);
    pull(id, l, r);
    ll mid = (l + r) / 2;
    update(st[id].l, i, j, x, l, mid);
    update(st[id].r, i, j, x, mid + 1, r);
    st[id].sum = st[st[id].l].sum + st[st[id].r].sum;
}

ll get(ll id, ll i, ll j, ll l = 1, ll r = ll(1e9)){
    if (r < i || l > j) return 0;
    if (i <= l && r <= j){
        return st[id].sum;
    }
    add_node(id);
    pull(id, l, r);
    ll mid = (l + r) / 2;
    return get(st[id].l, i, j, l, mid) + get(st[id].r, i, j, mid + 1, r);
}

void Init(){
    cin >> n;
    ll C = 0;
    for (ll i = 1; i <= n; ++i){
        ll t, x, y;
        cin >> t >> x >> y;
        x += C;
        y += C;
        if (t == 1){
            ll ans = get(1, x, y);
            C = ans;
            cout << ans << "\n";
        }
        else{
            update(1, x, y, 1);
        }
    }
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	200692 KB	Output is correct
2	Correct	82 ms	200668 KB	Output is correct
3	Correct	78 ms	200684 KB	Output is correct
4	Correct	86 ms	200652 KB	Output is correct
5	Correct	90 ms	200720 KB	Output is correct
6	Correct	99 ms	200780 KB	Output is correct
7	Correct	104 ms	200696 KB	Output is correct
8	Correct	155 ms	200872 KB	Output is correct
9	Correct	219 ms	201036 KB	Output is correct
10	Correct	231 ms	201020 KB	Output is correct
11	Correct	233 ms	200976 KB	Output is correct
12	Correct	261 ms	201040 KB	Output is correct
13	Correct	206 ms	201196 KB	Output is correct
14	Correct	223 ms	201140 KB	Output is correct
15	Correct	262 ms	201504 KB	Output is correct
16	Correct	316 ms	203296 KB	Output is correct
17	Correct	217 ms	203272 KB	Output is correct
18	Correct	231 ms	203228 KB	Output is correct
19	Correct	334 ms	203348 KB	Output is correct
20	Correct	315 ms	203272 KB	Output is correct