답안 #858435

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858435 2023-10-08T13:35:22 Z Requiem 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
379 ms 262144 KB
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "apple"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
struct SparseSegmentTree{
    int sum,lazy,l,r;
    SparseSegmentTree *toleft=NULL, *toright=NULL;
    SparseSegmentTree(): sum(0), lazy(-1), l(0), r(0) {}
    SparseSegmentTree(int l,int r): sum(0), lazy(-1), l(l), r(r){}
};
int cnt = 0;
SparseSegmentTree *root;
void push(SparseSegmentTree *root){
    if (root!=NULL){
        int mid = (root->l + root->r) / 2;
        if (root->toleft == NULL) root->toleft = new SparseSegmentTree(root->l,mid);
        if (root->toright == NULL) root->toright = new SparseSegmentTree(mid+1,root->r);
        if (root->lazy==1){
            root->sum = root->r  -  root->l +1;
            root->toleft->lazy = root->lazy;
            root->toright->lazy = root->lazy;
            root->lazy = -1;
        }
    }
}
void upd(SparseSegmentTree *root,int u,int v){
    push(root);
    if (root->l > v or root->r < u) return;
    if (root->l >= u and root->r <=v) {
        root->lazy = 1;
        push(root);
        return;
    }
    upd(root->toleft,u,v);
    upd(root->toright,u,v);
    root->sum = root->toleft->sum + root->toright->sum;
}
int get(SparseSegmentTree *root,int u,int v){
    push(root);
    if (root->l > v or root->r < u) return 0;
    if (root->l >= u and root->r <=v) return root->sum;
    return get(root->toleft,u,v) + get(root->toright,u,v);
}
int n;
main()
{
    fast;
  //  freopen(TASKNAME".inp","r",stdin);
  //  freopen(TASKNAME".out","w",stdout);
    int n;
    cin>>n;
    int c = 0;
    root = new SparseSegmentTree(1,1e9);
    for(int i=1;i<=n;i++){
        int type,x,y;
        cin>>type>>x>>y;
        if (type==1) {
            c = get(root,x+c,y+c);
            cout<<c<<endl;
        }
        else{
            upd(root,x+c,y+c);
        }
    }

}

Compilation message

apple.cpp:61:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   61 | main()
      | ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 16 ms 12612 KB Output is correct
5 Correct 20 ms 15196 KB Output is correct
6 Correct 19 ms 14684 KB Output is correct
7 Correct 19 ms 15184 KB Output is correct
8 Correct 162 ms 116680 KB Output is correct
9 Correct 334 ms 202392 KB Output is correct
10 Correct 343 ms 223828 KB Output is correct
11 Correct 367 ms 240472 KB Output is correct
12 Correct 379 ms 248100 KB Output is correct
13 Runtime error 313 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -