Submission #1200156

#TimeUsernameProblemLanguageResultExecution timeMemory
1200156henrllyMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
358 ms327680 KiB
// time-limit: 3000
#include <bits/stdc++.h>

using namespace std;

#define ll long long

using vll = vector<ll>;
using vvll = vector<vector<ll> >;
using mpll = map<pair<ll, ll>, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pi = pair<int, int>;

void setIO(string name = "") {
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

void solve() {
    return;
}


struct Node {
    Node *left = nullptr;
    Node *right = nullptr;
    ll cur = 0;
    ll lazy = 0;
};

const ll MAXN = 1000000000;

void apply(Node *n, int len, int val) {
    n->cur += val * len;
    n->lazy += val;
}

void push_down(Node *n, int l, int r) {
    if (n == nullptr || n->lazy == 0) return;
    if (n->left == nullptr) n->left = new Node;
    if (n->right == nullptr) n->right = new Node;
    int mid = (l+r)/2;
    apply(n->left, mid-l+1, n->lazy);
    apply(n->right, r-mid, n->lazy);
    n->lazy = 0;
}

ll range(Node *n, int li, int ri, int l=0, int r=MAXN-1) {
    if (n == nullptr) return 0ll;
    push_down(n, l, r);
    if (li <= l && ri >= r) return n->cur;
    if (li > r || ri < l) return 0ll;
    int mid = (l+r)/2;
    ll res = range(n->left, li, ri, l, mid) + range(n->right, li, ri, mid+1, r);
    n->cur = (n->left == nullptr ? 0 : n->left->cur) + (n->right == nullptr ? 0 : n->right->cur);
    return res;
}

void ripe(Node *n, int li, int ri, int l=0, int r=MAXN-1, Node *p=nullptr, int leftf=0) {
    push_down(n, l, r);
    if (li > r || ri < l) return;
    if (n == nullptr) {
        if (leftf) {p->left = new Node; n = p->left;}
        else {p->right = new Node; n = p->right;}
    }
    if (li <= l && ri >= r) {
        n->cur = r-l+1;
        n->lazy = 1;
        delete n->left;
        n->left = nullptr;
        delete n->right;
        n->right = nullptr;
        return;
    }
    int mid = (l+r)/2;
    ripe(n->left, li, ri, l, mid, n, 1);
    ripe(n->right, li, ri, mid+1, r, n, 0);
    n->cur = (n->left == nullptr ? 0 : n->left->cur) + (n->right == nullptr ? 0 : n->right->cur);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // setIO("test");

    int m; cin >> m;
    ll c = 0;
    Node root;
    while (m--) {
        int t, a, b; cin >> t >> a >> b;
        a--;b--;
        if (t == 1) {
            c = range(&root, a+c, b+c);
            cout << c << endl;
        } else {
            ripe(&root, a+c, b+c);
        }
    }

    return 0;
}

Compilation message (stderr)

apple.cpp: In function 'void setIO(std::string)':
apple.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...