Submission #917107

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
917107	2024-01-27T08:14:46 Z	script_kidd	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	342 ms	207956 KB

apple

//#pragma GCC optimize("O3,Ofast,unroll-loops")
//#pragma GCC target("avx2")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
//#define int long long
//#define double long double
//const int INF=2e18;
//#define ll long long
//const int INF=2e9;

using namespace std;
using namespace __gnu_pbds;
using pii=pair<int, int>;
using vi=vector<int>;
using vvi=vector<vector<int>>;


#define FOR(x,n) for(int x=0; x<n; x++)
#define FOR1(x,n) for(int x=1; x<=n; x++)
#define REV(x,n) for(int x=n; x-->0;)
#define REV1(x,n) for(int x=n; x>0; i--)

#define SZ(X) (int)(X.size())
#define pb push_back
#define lb lower_bound
#define mp make_pair
#define all(v) begin(v), end(v)
#define UNTIE_IO ios_base::sync_with_stdio(0);cin.tie(0);

const int MOD=998244353;
const int SIZE=1e9;


int Q;

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

struct Seg {
    int l, r, m, sz, val, lz;
    Seg* ch[2];
    Seg (int _l, int _r): l(_l), r(_r), m((l+r)>>1), sz(r-l+1), val(0), lz(0){
        ch[0] = ch[1] = nullptr;
    }

    void pull(){
        val = ch[0]->val + ch[1]->val;
    }

    void give(int t){
        if (t){
            lz = t;
            val = t*sz;
        }
    }

    void push(){
        if (ch[0] == nullptr){
            ch[0] = new Seg(l, m);
        }
        ch[0]->give(lz);

        if (ch[1] == nullptr){
            ch[1] = new Seg(m+1, r);
        }
        ch[1]->give(lz);

        lz = 0;
    }

    void upd(int ql, int qr, int x){
        if (ql <= l && r <= qr){
            give(x);
            return;
        }
        push();
        if (ql<=m) ch[0]->upd(ql, qr, x);
        if (m<qr) ch[1]->upd(ql, qr, x);
        pull();
    }

    int qry(int ql, int qr){
        if (ql <= l && r <= qr){
            return val;
        }
        push();
        int res = 0;
        if (ql<=m) res += ch[0]->qry(ql, qr);
        if (m<qr) res += ch[1]->qry(ql, qr);
        return res;
    }

};


signed main(){
    UNTIE_IO;

    Seg rt(1, SIZE);
    int C = 0;
    cin>>Q;
    while (Q--){
        int t,l,r;
        cin>>t>>l>>r;
        if (t==1){
            auto res = rt.qry(l+C, r+C);
            cout << res << '\n';
            C = res;
        }
        else {
            rt.upd(l+C, r+C, 1);
        }
    }
}

Compilation message

apple.cpp: In function 'void setIO(std::string)':
apple.cpp:38:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	9 ms	4956 KB	Output is correct
5	Correct	11 ms	5980 KB	Output is correct
6	Correct	11 ms	5976 KB	Output is correct
7	Correct	11 ms	5980 KB	Output is correct
8	Correct	87 ms	44480 KB	Output is correct
9	Correct	197 ms	75508 KB	Output is correct
10	Correct	205 ms	85732 KB	Output is correct
11	Correct	211 ms	91640 KB	Output is correct
12	Correct	221 ms	94476 KB	Output is correct
13	Correct	194 ms	110164 KB	Output is correct
14	Correct	186 ms	111180 KB	Output is correct
15	Correct	317 ms	201812 KB	Output is correct
16	Correct	324 ms	203348 KB	Output is correct
17	Correct	215 ms	114908 KB	Output is correct
18	Correct	195 ms	114772 KB	Output is correct
19	Correct	333 ms	207696 KB	Output is correct
20	Correct	342 ms	207956 KB	Output is correct