Submission #566355

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
566355	2022-05-22T09:14:02 Z	Aldas25	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	421 ms	262144 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;
    pt leCh;
    pt riCh;

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

    void upd () {
        if (le == ri) return;
        ll m = (le+ri)/2;
        if (!leCh) leCh = new node (le, m);
        if (!riCh) riCh = new node (m+1, ri);
    }

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

void shift (pt cur) {
    if ((cur->lazy) == 0) return;
    cur->lazy = 0;
    cur->leCh->turn();
    cur->riCh->turn();
}

pt root = new node (0, 1e9+5);

void upd (ll x, ll y, pt cur = root) {
    if (x > (cur->ri) || (cur->le) > y) return;
    if (x <= (cur->le) && (cur->ri) <= y) {
        cur->turn();
        return;
    }
    cur->upd();
    shift (cur);
    upd (x, y, cur->leCh);
    upd (x, y, cur->riCh);
    cur->sum = (cur->leCh->sum) + (cur->riCh->sum);
}

ll get (ll x, ll y, pt cur = root) {
    if (x > (cur->ri) || (cur->le) > y) return 0;
    if (x <= (cur->le) && (cur->ri) <= y) return cur->sum;
    cur->upd();
    shift (cur);
    return get(x, y, cur->leCh) + get(x, y, cur->riCh);
}

int main()
{
    setIO();

    int q; cin >> q;
    ll c = 0;
    while (q--) {
        int d; ll x, y;
        cin >> d >> x >> y;
        x += c;
        y += c;
        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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	12 ms	6440 KB	Output is correct
5	Correct	15 ms	7892 KB	Output is correct
6	Correct	15 ms	7508 KB	Output is correct
7	Correct	16 ms	7892 KB	Output is correct
8	Correct	129 ms	58876 KB	Output is correct
9	Correct	243 ms	102360 KB	Output is correct
10	Correct	250 ms	113108 KB	Output is correct
11	Correct	268 ms	121400 KB	Output is correct
12	Correct	266 ms	125120 KB	Output is correct
13	Correct	239 ms	145740 KB	Output is correct
14	Correct	242 ms	147248 KB	Output is correct
15	Runtime error	421 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-