Submission #519990

#	Time	Username	Problem	Language	Result	Execution time	Memory
519990		XII	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	402 ms	153404 KiB

apple

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "IZhO12_apple"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int M = 1e5 + 1;
struct node{
    int sum, lz, be, en, l, r;
    node(): sum(0), lz(0), l(-1), r(-1) {}
};
node ST[M * 64];
int cnt = 1;

void down(const int &id){
    int mi = (ST[id].be + ST[id].en) / 2;
    if(ST[id].l == -1){
        ST[id].l = ++cnt;
        ST[cnt].be = ST[id].be;
        ST[cnt].en = mi;
    }
    if(ST[id].r == -1){
        ST[id].r = ++cnt;
        ST[cnt].be = mi + 1;
        ST[cnt].en = ST[id].en;
    }
    if(ST[id].lz){
        ST[ST[id].l].lz = ST[ST[id].r].lz = ST[id].lz;
        ST[ST[id].l].sum = (mi - ST[id].be + 1);
        ST[ST[id].r].sum = (ST[id].en - mi);
        ST[id].lz = 0;
    }
}

void update(const int &l, const int &r, const int &v, int id = 1){
    if(l <= ST[id].be && ST[id].en <= r){
        ST[id].sum = (ST[id].en - ST[id].be + 1);
        ST[id].lz = 1;
        return;
    }
    int mi = (ST[id].be + ST[id].en) / 2;
    if(ST[id].l == -1){
        ST[id].l = ++cnt;
        ST[cnt].be = ST[id].be;
        ST[cnt].en = mi;
    }
    if(ST[id].r == -1){
        ST[id].r = ++cnt;
        ST[cnt].be = mi + 1;
        ST[cnt].en = ST[id].en;
    }
    down(id);
    if(l <= mi) update(l, r, v, ST[id].l);
    if(mi < r) update(l, r, v, ST[id]. r);
    ST[id].sum = ST[ST[id].l].sum + ST[ST[id].r].sum;
}

int query(const int &l, const int &r, int id = 1){
    if(l <= ST[id].be && ST[id].en <= r) return ST[id].sum;
    int mi = (ST[id].be + ST[id].en) / 2;
    down(id);
    int ret = 0;
    if(l <= mi) ret += query(l, r, ST[id].l);
    if(mi < r) ret += query(l, r, ST[id].r);
    return ret;
}

int C;

int main(){
    IOS;
    Fi();
    int m; cin >> m;
    ST[1].be = 1, ST[1].en = 1e9;
    while(m--){
        int t, x, y; cin >> t >> x >> y;
        if(t == 2) update(x + C, y + C, 1);
        else cout << (C = query(x + C, y + C)) << "\n";
    }
    return 0;
}

Compilation message (stderr)

apple.cpp: In function 'void Fi()':
apple.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100