Submission #411070

# Submission time Handle Problem Language Result Execution time Memory
411070 2021-05-24T08:58:53 Z zipdang04 Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
1 ms 204 KB
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;

/*
struct Node
{
    int node, len;
    Node() {node = len = 0;}
    Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
*/


#define MOD 1000000007

#define fi first
#define se second
#define pf push_front
#define pb push_back

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

#define testBit(n, bit) ((n >> bit) & 1)
#define flipBit(n, bit) (n ^ (1ll << bit))
#define cntBit(n) __builtin_popcount(n)
#define cntBitll(n) __builtin_popcountll(n)
#define randomize mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

const ll MAX = 1e18;
class Node{
    private:
        ll lo, hi, cnt;
        bool stop;
        Node *left, *right;
    public:
        Node(ll lo, ll hi): lo(lo), hi(hi){
            cnt = 0; stop = true;
            left = nullptr, right = nullptr;
        }
        Node(): Node(1, MAX){}

        void update(ll posL, ll posR){
            if (posR < lo || hi < posL) return;
            if (posL <= lo && hi <= posR){
                cnt = hi - lo + 1;
                stop = true;
                delete left; left = nullptr; 
                delete right; right = nullptr;
                return;
            }

            if (stop){
                if (cnt) return; 
                stop = false;
                ll mid = (lo + hi) >> 1;
                left = new Node(lo, mid);
                right = new Node(mid + 1, hi);
            }

            left -> update(posL, posR);
            right -> update(posL, posR);
            cnt = left -> cnt + right -> cnt;
        }

        ll get(ll posL, ll posR){
            if (posR < lo || hi < posL) return 0;
            if (posL <= lo && hi <= posR) return cnt;

            if (stop){
                if (!cnt) return 0;
                if (posR <= hi) 
                    return posR - lo + 1;
                else 
                    return hi - posL + 1;
            }

            return left -> get(posL, posR) + right -> get(posL, posR);
        }
};

Node *root = new Node();
ll m, c;

main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> m; c = 0;
    FOR(ll, _, 1, m){
        ll d, x, y; cin >> d >> x >> y;
        if (d == 1){
            c = root -> get(x + c, y + c);
            cout << c << '\n';
        } else
            root -> update(x + c, y + c);
    }
}

Compilation message

apple.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  103 | main()
      | ^~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -