Submission #917108

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
917108	2024-01-27T08:17:40 Z	script_kidd	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	354 ms	205988 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;      // Update tag
            val = t*sz;  // Update value
        }
    }

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

        if (!ch[1]) 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	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	9 ms	4956 KB	Output is correct
5	Correct	11 ms	5976 KB	Output is correct
6	Correct	11 ms	5724 KB	Output is correct
7	Correct	11 ms	5980 KB	Output is correct
8	Correct	89 ms	43732 KB	Output is correct
9	Correct	198 ms	75600 KB	Output is correct
10	Correct	201 ms	83624 KB	Output is correct
11	Correct	209 ms	90268 KB	Output is correct
12	Correct	204 ms	92760 KB	Output is correct
13	Correct	184 ms	108076 KB	Output is correct
14	Correct	190 ms	109140 KB	Output is correct
15	Correct	312 ms	199768 KB	Output is correct
16	Correct	327 ms	201048 KB	Output is correct
17	Correct	189 ms	112724 KB	Output is correct
18	Correct	197 ms	112848 KB	Output is correct
19	Correct	330 ms	205988 KB	Output is correct
20	Correct	354 ms	205652 KB	Output is correct