Submission #713810

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713810	2023-03-23T05:18:07 Z	swagchicken	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	503 ms	232904 KB

apple

#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 
template <typename T>
void pr(vector<T> &v) {
    FOR(i, 0, sz(v)) cout << v[i] << " ";
    cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
    FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
    cin >> x;
}
template <typename T>
void re(vector<T> &a) {
    FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
    re(first);
    re(rest...);
}
template <typename T>
void pr(T x) {
    cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
    cout << first << " ";
    pr(rest...);
    cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
    cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
 
const ll MOD  = 998244353;
#define inf 1e18;
#define INF INT_MAX

long double PI = 4*atan(1);
long double eps = 1e-12;


ll MX_SZ = 1000000010;
template <class T>
struct node {
    T val;
    T lazy;
    node* c[2];

    node() {
        c[0] = c[1] = nullptr;
        val = 0;
        lazy = -1;
    }

    void prop(ll L, ll R) {
        if(lazy != -1) {
            val = (R - L + 1) * lazy;
            if(L != R) {
                if(c[0] == nullptr) c[0] = new node();
                c[0]->lazy = lazy;

                if(c[1] == nullptr) c[1] = new node();
                c[1]->lazy = lazy;
            }
            
            lazy = -1;
        }
    }

    void update(T v, ll ul, ll ur,ll L=0, ll R=MX_SZ) {
        prop(L, R);
        if(ur < L || R < ul || R < L) return;
        if(ul <= L && R <= ur) {
            lazy = v;
            prop(L, R);
            return;
        }
        
        ll M = (L + R)/2;
        if(c[0] == nullptr) c[0] = new node();
        c[0]->update(v, ul, ur, L, M);
        if(c[1] == nullptr) c[1] = new node();
        c[1]->update(v, ul, ur, M+1, R);
        
        val = 0;
        if(c[0] != nullptr) val += c[0]->val;
        if(c[1] != nullptr) val += c[1]->val;
    }

    T query(ll ql, ll qr, ll L=0, ll R=MX_SZ) {
        if(qr < L || R < ql || R < L) return 0;
        prop(L, R);
        if(ql <= L && R <= qr) return val;
        ll M = (L + R)/2, ans = 0;
        if(c[0] != nullptr) ans += c[0]->query(ql, qr, L, M);
        if(c[1] != nullptr) ans += c[1]->query(ql, qr, M+1, R);
        return ans;
    }
};

int main() {
    //auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    //ofstream cout("output.txt");
    //ifstream cin("input.txt");
    #ifdef DEBUG
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #endif  

    node<int> st;

    int m; cin >> m;
    ll c = 0;
    FOR(i,0,m) {
        int t; cin >> t;
        ll l,r; cin >> l >> r;
        if(t == 1) {
            ll ans =  st.query(l + c, r + c);
            cout << ans << endl;
            c = ans;
        } else {
            st.update(1, l + c, r + c);
        }
    }



    
    
    //auto stop = chrono::high_resolution_clock::now();
    //auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    //cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	3 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	18 ms	5204 KB	Output is correct
5	Correct	17 ms	6228 KB	Output is correct
6	Correct	18 ms	6100 KB	Output is correct
7	Correct	20 ms	6228 KB	Output is correct
8	Correct	137 ms	46300 KB	Output is correct
9	Correct	308 ms	79332 KB	Output is correct
10	Correct	283 ms	88560 KB	Output is correct
11	Correct	318 ms	95964 KB	Output is correct
12	Correct	335 ms	99156 KB	Output is correct
13	Correct	286 ms	121304 KB	Output is correct
14	Correct	304 ms	122564 KB	Output is correct
15	Correct	475 ms	225868 KB	Output is correct
16	Correct	458 ms	227416 KB	Output is correct
17	Correct	299 ms	128960 KB	Output is correct
18	Correct	295 ms	128936 KB	Output is correct
19	Correct	503 ms	232904 KB	Output is correct
20	Correct	471 ms	232572 KB	Output is correct