Submission #566371

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
566371	2022-05-22T09:25:38 Z	Aldas25	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	335 ms	173648 KB

apple

/*
//#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
*/

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 500100, MAXK = 20;
const ll INF = 1e18;
//const ll MOD = 1e9+7;
const ll MOD = 998244353;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

typedef struct node * pt;

struct node {
    ll le, ri;
    ll sum;
    ll lazy;
    int leCh;
    int riCh;

    node () {}

    node (ll _le, ll _ri) {
        le = _le;
        ri = _ri;
        sum = 0;
        lazy = 0;
        leCh = 0;
        riCh = 0;
    }

    void turn () {
        lazy = 1;
        sum = (ri) - (le) + 1;
    }
};

node tree[100*100*1000];
int crId = 0;

int newNode (int le, int ri) {
    ++crId;
    tree[crId] = node (le, ri);
    return crId;
}

void nodeupd (int id) {
    if (tree[id].le == tree[id].ri) return;
    ll m = ((tree[id].le)+(tree[id].ri))/2;
    if (!(tree[id].leCh)) tree[id].leCh = newNode (tree[id].le, m);
    if (!(tree[id].riCh)) tree[id].riCh = newNode (m+1, tree[id].ri);
}

void shift (int cur) {
    if ((tree[cur].lazy) == 0) return;
    tree[cur].lazy = 0;
    tree[tree[cur].leCh].turn();
    tree[tree[cur].riCh].turn();
}

int root;

void upd (ll x, ll y, int cur = root) {
    if (x > (tree[cur].ri) || (tree[cur].le) > y) return;
    if (x <= (tree[cur].le) && (tree[cur].ri) <= y) {
        tree[cur].turn();
        return;
    }
    nodeupd(cur);
    shift (cur);
    upd (x, y, tree[cur].leCh);
    upd (x, y, tree[cur].riCh);
    tree[cur].sum = (tree[tree[cur].leCh].sum) + (tree[tree[cur].riCh].sum);
}

ll get (ll x, ll y, int cur = root) {
    if (x > (tree[cur].ri) || (tree[cur].le) > y) return 0;
    if (x <= (tree[cur].le) && (tree[cur].ri) <= y) return tree[cur].sum;
    nodeupd(cur);
    shift (cur);
    return get(x, y, tree[cur].leCh) + get(x, y, tree[cur].riCh);
}

int main()
{
    setIO();

    root = newNode (0, 1e9+5);

    int q; cin >> q;
    ll c = 0;
    while (q--) {
        int d; ll x, y;
        cin >> d >> x >> y;
        x += c;
        y += c;
       // if (y > 1e6+1) exit(0);
        if (d == 1) {
            c = get(x,y);
            cout << c << "\n";
        } else upd(x,y);
    }

    return 0;
}

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	16 ms	4156 KB	Output is correct
5	Correct	16 ms	5080 KB	Output is correct
6	Correct	14 ms	4948 KB	Output is correct
7	Correct	14 ms	5084 KB	Output is correct
8	Correct	103 ms	37352 KB	Output is correct
9	Correct	243 ms	64864 KB	Output is correct
10	Correct	233 ms	71372 KB	Output is correct
11	Correct	273 ms	76608 KB	Output is correct
12	Correct	244 ms	78964 KB	Output is correct
13	Correct	220 ms	91720 KB	Output is correct
14	Correct	233 ms	92596 KB	Output is correct
15	Correct	310 ms	168648 KB	Output is correct
16	Correct	335 ms	169808 KB	Output is correct
17	Correct	243 ms	96092 KB	Output is correct
18	Correct	222 ms	96156 KB	Output is correct
19	Correct	335 ms	173568 KB	Output is correct
20	Correct	322 ms	173648 KB	Output is correct