Submission #411033

#	Time	Username	Problem	Language	Result	Execution time	Memory
411033		zipdang04	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	204 KiB

apple

#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<int, 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 int MAX = 1000000000;
class Node{
    private:
        Node *left, *right;
        bool stop;
        int lo, hi, cnt;

    public:
        Node(int lo, int hi, bool all = false): lo(lo), hi(hi){
            left = nullptr, right = nullptr;
            stop = true;
            cnt = all ? (hi - lo + 1) : 0;
        }
        Node(): Node(1, MAX){}

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

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

            left -> ripen(posL, posR);
            right -> ripen(posL, posR);
            cnt = left -> cnt + right -> cnt;
        }
        int get(int posL, int posR){
            if (hi < posL || posR < lo) return 0;
            // cerr << lo << '/' << hi << ' ' << stop << '.' << cnt << '\n';
            if (posL <= lo && hi <= posR) return cnt;
            // cerr << "someOut\n";

            if (this -> stop){
                if (cnt == 0) return 0;
                if (posR <= hi)
                    return posR - lo + 1;
                else
                    return hi - posL + 1;
            }
            // cerr << "nonstop\n";

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

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

Compilation message (stderr)

apple.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main()
      | ^~~~

• Subtask 1: 0 / 100