Submission #930578

# Submission time Handle Problem Language Result Execution time Memory
930578 2024-02-20T07:09:14 Z dosts Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
271 ms 344 KB
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define ff first
#define ss second
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
template<typename T1, typename T2> bool MIN(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<typename T1, typename T2> bool MAX(T1 &a, T2 b){return a < b ? a = b, true : false;}
const int N = 2e5+1;
int L,R;
struct DST {
    int l,r,v=0,lazy=0;
    DST* c[2];
    DST(int lll,int rrr): l(lll),r(rrr),c{NULL,NULL}{};

    void push() {
        v = r-l+1;
        if (l != r) {
            int m = (l+r) >> 1;
            if (!c[0]) c[0] = new DST(l,m);
            if (!c[1]) c[1] = new DST(m+1,r);
            c[0]->lazy = 1;
            c[1]->lazy = 1;
        }
        lazy = 0;
    }

    int query() {
        //cout << l sp r sp v sp lazy << '\n';
        if (lazy) push();
        if (l >= L && r <= R) return v;
        int m =  (l+r) >> 1,ans = 0;
        if (R >= m+1 && c[1]) ans+=c[1]->query();
        if (L <= m && c[0]) ans+=c[0]->query();
        return ans;
    }

    void update() {
        //cout << l sp r sp v sp lazy << '\n';
        if (lazy) push();
        if (l >= L && r <= R) {
            //cout << "PUSHING: " << l sp r << '\n';
            lazy=1;
            push();
            return;
        } 
        int m = (l+r) >> 1;
        if (R >= m+1) {
            if (!c[1]) c[1] =  new DST(m+1,r);
            c[1]->update();
        }
        if (L <= m) {
            if (!c[0]) c[0] = new DST(l,m);
            c[0]->update();
        }
        v = 0;
        if (c[0]) {
            if (c[0]->lazy) c[0]->push();
            v+=c[0]->v;
        }
        if (c[1]) {
            if (c[1]->lazy) c[1]->push();
            v+=c[1]->v;
        }
    }
};

void solve() {  
    DST DoST(1,1e9);
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l,r;
            cin >> l >> r;
            l+=c;
            r+=c;
            L = l;
            R = r;
            c = DoST.query();
            cout << c << '\n';
        }
        else {
            int l,r;
            cin >> l >> r;
            l+=c;
            r+=c;
            L = l;
            R = r;
            DoST.update();
        }
    }
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifndef Dodi
        freopen("snowcow.in","r",stdin);
        freopen("snowcow.out","w",stdout);
    #else
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif

    int t = 1;
    //cin >> t; 
	while (t --> 0) solve();
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen("snowcow.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen("snowcow.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 271 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -