oj.uz

답안 #672513

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
672513 2022-12-16T11:46:18 Z bLIC 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 370 ms 202756 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

// typedef tree<int,null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back
#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;

#define dbg if(0)

const ll MOD = 998244353;
const ll INFLL = 1e18;
const int INF = 1e9;
const int maxN = 2e5+6;
const int maxK = 10;

void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}


#define gbit(x, i) (((1<<i)&(x))!=0)


struct Node{
    int lx, rx;
    ll sm;
    bool lz;
    Node *lt, *rt;
    Node(ll x, ll l, ll r):sm(x), lx(l), rx(r), lz(0), lt(NULL), rt(NULL){}
    Node(ll l, ll r): Node(0, l, r){}
    void pushdown(){
        if (lz==0) return;
        ll mid = (lx+rx)/2;
        lt->sm = mid-lx;
        rt->sm = rx-mid;
        lt->lz = 1;
        rt->lz = 1;
        lz = 0;
    }
    void pushup(){
        sm = lt->sm+rt->sm;
    }
    void upd(ll l, ll r, ll val){
        if (l<=lx && rx<=r) {
            sm = (rx-lx);
            lz = 1;
            return;
        }
        if (l>=rx || r<=lx) return;
        ll mid = (lx+rx)/2;
        if (!lt) lt = new Node(lx, mid);
        if (!rt) rt = new Node(mid, rx);
        pushdown();
        lt->upd(l, r, val);
        rt->upd(l, r, val);
        pushup();
    }
    ll query(int l, int r){
        if (l<=lx && rx<=r) return sm;
        if (l>=rx || r<=lx) return 0;
        ll mid = (lx+rx)/2;
        if (!lt) lt = new Node(lx, mid);
        if (!rt) rt = new Node(mid, rx);
        pushdown();
        ll ans = lt->query(l, r) + rt->query(l, r);
        pushup();
        return ans;
    }
};

template <class T>
istream& operator>>(istream& in, vector<T>& v){
    for (T& x:v) in>>x;
    return in;
}

const ll MAXN = 1ll<<30;
void solve(){
    int n;cin>>n;
    int c = 0;

    Node* root = new Node(0, MAXN);
    while(n--){
        int t;cin>>t;
        int x, y;cin>>x>>y;
        if (t==1){
            c = root->query(x-1+c, y+c);
            cout<<c<<"\n";
        }
        else {
            root->upd(x-1+c, y+c, 1);
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
// #define _DEBUG
#ifdef _DEBUG
	freopen("haybales.in", "r", stdin);
	freopen("haybales.out", "w", stdout);
	int tt = clock();
#endif
    int t=1, i = 1;
    // cin>>t;
    while(t--){
        // cout<<"Case #"<<i++<<": ";
        solve();
        // cout<<'\n';
    }
#ifdef _DEBUG
    cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
    tt = clock();
#endif
}

Compilation message

apple.cpp: In constructor 'Node::Node(ll, ll, ll)':
apple.cpp:45:8: warning: 'Node::sm' will be initialized after [-Wreorder]
   45 |     ll sm;
      |        ^~
apple.cpp:44:9: warning:   'int Node::lx' [-Wreorder]
   44 |     int lx, rx;
      |         ^~
apple.cpp:48:5: warning:   when initialized here [-Wreorder]
   48 |     Node(ll x, ll l, ll r):sm(x), lx(l), rx(r), lz(0), lt(NULL), rt(NULL){}
      |     ^~~~
apple.cpp: In function 'int main()':
apple.cpp:126:14: warning: unused variable 'i' [-Wunused-variable]
  126 |     int t=1, i = 1;
      |              ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 11 ms 4704 KB Output is correct
5 Correct 13 ms 5560 KB Output is correct
6 Correct 13 ms 5452 KB Output is correct
7 Correct 16 ms 5592 KB Output is correct
8 Correct 108 ms 41908 KB Output is correct
9 Correct 226 ms 74908 KB Output is correct
10 Correct 238 ms 80160 KB Output is correct
11 Correct 240 ms 86352 KB Output is correct
12 Correct 236 ms 88952 KB Output is correct
13 Correct 219 ms 105368 KB Output is correct
14 Correct 222 ms 106396 KB Output is correct
15 Correct 366 ms 194436 KB Output is correct
16 Correct 353 ms 196912 KB Output is correct
17 Correct 221 ms 110120 KB Output is correct
18 Correct 230 ms 110052 KB Output is correct
19 Correct 370 ms 202596 KB Output is correct
20 Correct 362 ms 202756 KB Output is correct