Submission #919830

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919830	2024-02-01T17:19:47 Z	QioCas	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	756 KB

apple

#include <bits/stdc++.h> // QioCas

#ifdef LOCAL
#include </home/cas/Cp/Lib/debug.h>
#else
#define console(...) void(202421)
#endif

using namespace std;
using ll = long long;

int Q; 

struct node_t {
    int sum = 0, maxL = 0, maxR = 0, ans = 0, lz = 0;
    node_t *l = nullptr, *r = nullptr;
    void update(node_t* u, node_t* v) {
        sum = u->sum + v->sum;
        maxL = max(u->maxL, (u->lz != 0 ? u->sum + v->maxL : 0));
        maxR = max(v->maxR, (v->lz != 0 ? v->sum + u->maxR : 0));
        ans = max(u->ans + v->ans, u->maxR + v->maxL);
    }
};

using pnode = node_t*;

void update_node(pnode& IT, int l, int r) {
    if(!IT) IT = new node_t();
    IT->sum = IT->maxL = IT->maxR = IT->ans = r - l + 1;
    IT->lz = 1;
}

void push_down(pnode& IT, int l, int r) {
    if(IT->lz == 0) return;
    if(IT->lz == 1) {
        int mid = (l + r) / 2;
        update_node(IT->l, l, mid);
        update_node(IT->r, mid + 1, r);
    }
    IT->lz = 2;
}

void update(pnode& IT, int l, int r, int s, int t) {
    if(!IT) IT = new node_t();
    if(l > t || r < s) return;
    if(s <= l && r <= t) {
        update_node(IT, l, r);
        return;
    } push_down(IT, l, r);
    int mid = (l + r) / 2;
    update(IT->l, l, mid, s, t);
    update(IT->r, mid + 1, r, s, t);
    IT->update(IT->l, IT->r);    
}

pnode prod(pnode& IT, int l, int r, int s, int t) {
    if(!IT || l > t || r < s) return new node_t();
    if(s <= l && r <= t) return IT;
    push_down(IT, l, r);
    int mid = (l + r) / 2;
    pnode ret = new node_t();
    ret->update(prod(IT->l, l, mid, s, t), prod(IT->r, mid + 1, r, s, t));
    return ret;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);

    cin >> Q;

    ll c = 0;

    pnode root = new node_t();
    int L = 1, R = 1e9;

    while(Q--) {
        int op; ll l, r;
        cin >> op >> l >> r;
        l += c; r += c;
        if(op == 2) {
            update(root, L, R, l, r);
        } else {
            int x = prod(root, L, R, l, r)->ans;
            cout << x << "\n";
            c += x;
        }
    }
    return 0;
}

////////////////////////////////////////////////////////////////////////////
//  Nhân quả không nợ chúng ta thức gì, cho nên xin đừng oán giận   ////////
//                                   _
//                                _oo0oo_
//                               o8888888o
//                               88” . “88
//                               (| -_- |)
//                               O\  =  /O
//                            ____/'---'\____
//                          .'  \\|     |//  '.
//                         /  \\|||  :  |||//  \
//                        /  _||||| -:- |||||_  \
//                        |   | \\\  -  /'| |   |
//                        | \_|  `\`---'//  |_/ |
//                        \  .-\__ `-. -'__/-.  /
//                      ___`. .'  /--.--\  `. . '___
//                   ."" '<  `.___\_<|>_/___.'  _> \"".
//                  | | :  `- \`. ;`. _/; .'/  /  .' ; |
//                  \  \ `-.   \_\_`. _.' _/_/  -' _.' /
//===================`-.`___`-.__\ \___   /__.-'_.'_.-'===================//
//                                `=--=-'
 
// Đức Phật nơi đây phù hộ code con chạy không Bugs. Nam mô a di đà Phật.
 
//
//                      _.-/`)
//                     // / / )
//                  .=// / / / )
//                 //`/ / / / /
//                // /    `  /
//               ||         /
//              ||         /
//               \\       /
//                ))    .'
//               //     /
//

Compilation message

apple.cpp:101:1: warning: multi-line comment [-Wcomment]
  101 | //                         /  \\|||  :  |||//  \
      | ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Incorrect	1 ms	756 KB	Output isn't correct
3	Halted	0 ms	0 KB	-