oj.uz

답안 #568874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568874 2022-05-26T09:53:06 Z Dan4Life 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 592 ms 202252 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll // delete if causing problems
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define mod(a) (a+MOD)%MOD
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define what_is(x) cerr << #x << " is " << x << "\n"

const int maxn = (int)3e5+10; // change when needed!
const int MOD = (int)1e9+7; // same!
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
int n, m, x, y, l, r, k, q, t;
map<int, int> M, N;
multiset<int> S, SS;
string s, ss;
vector<int> segTree, lazy;
vector<pair<int,int>> child;
int IND = 0;

void add_node(int v=0, int le=-1, int ri=-1, int lz=LINF){
    segTree.pb(v); child.pb({le,ri}); lazy.pb(lz);
}

void propagate(int p, int l, int r){
    if(p==-1 or l==r or lazy[p]==LINF) return;
    int mid = (l+r)/2;
    if(child[p].fi!=-1) lazy[child[p].fi]=lazy[p], segTree[child[p].fi]=lazy[p]*(mid-l+1);
    else child[p].fi= ++IND, add_node(lazy[p]*(mid-l+1),-1,-1,lazy[p]);
    if(child[p].se!=-1) lazy[child[p].se]=lazy[p], segTree[child[p].se]=lazy[p]*(r-mid);
    else child[p].se= ++IND, add_node(lazy[p]*(r-mid),-1,-1,lazy[p]);
    lazy[p] = LINF;
}

void update(int i, int j, int v, int p=0, int l=1, int r=INF){
    if(i>r or j<l or i>j or p==-1) return; propagate(p,l,r);
    if(i<=l and r<=j){ segTree[p] = v*(r-l+1); lazy[p] = v; return; }
    int mid = (l+r)/2;
    if(child[p].fi==-1) child[p].fi= ++IND, add_node();
    update(i,j,v,child[p].fi,l,mid);
    if(child[p].se==-1) child[p].se= ++IND, add_node();
    update(i,j,v,child[p].se,mid+1,r);
    int left = child[p].fi==-1?0:segTree[child[p].fi];
    int right = child[p].se==-1?0:segTree[child[p].se];
    segTree[p] = left+right;
}

int query(int i, int j, int p=0, int l=1, int r=INF){
    if(i>r or j<l or i>j or p==-1) return 0; propagate(p,l,r);
    if(i<=l and r<=j) return segTree[p];
    int mid = (l+r)/2;
    return query(i,j,child[p].fi,l,mid)+query(i,j,child[p].se,mid+1,r);
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> q; int c = 0; add_node();
    while(q--){
        int t, x, y; cin >> t >> x >> y; x+=c, y+=c;
        if(t==1){ c = query(x,y); cout << c << "\n"; }
        else update(x,y,1);
    }
}

Compilation message

apple.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
apple.cpp:42:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   42 |     if(i>r or j<l or i>j or p==-1) return; propagate(p,l,r);
      |     ^~
apple.cpp:42:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   42 |     if(i>r or j<l or i>j or p==-1) return; propagate(p,l,r);
      |                                            ^~~~~~~~~
apple.cpp: In function 'll query(ll, ll, ll, ll, ll)':
apple.cpp:55:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   55 |     if(i>r or j<l or i>j or p==-1) return 0; propagate(p,l,r);
      |     ^~
apple.cpp:55:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   55 |     if(i>r or j<l or i>j or p==-1) return 0; propagate(p,l,r);
      |                                              ^~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 18 ms 7596 KB Output is correct
5 Correct 20 ms 7732 KB Output is correct
6 Correct 23 ms 7732 KB Output is correct
7 Correct 23 ms 7728 KB Output is correct
8 Correct 170 ms 58788 KB Output is correct
9 Correct 353 ms 117308 KB Output is correct
10 Correct 372 ms 117324 KB Output is correct
11 Correct 367 ms 117020 KB Output is correct
12 Correct 379 ms 116988 KB Output is correct
13 Correct 339 ms 116876 KB Output is correct
14 Correct 344 ms 116932 KB Output is correct
15 Correct 543 ms 199368 KB Output is correct
16 Correct 550 ms 199292 KB Output is correct
17 Correct 349 ms 116908 KB Output is correct
18 Correct 355 ms 117052 KB Output is correct
19 Correct 580 ms 202252 KB Output is correct
20 Correct 592 ms 202184 KB Output is correct