답안 #840299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840299 2023-08-31T09:35:41 Z taitruong270 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
317 ms 262144 KB
/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
                                       Where is the bug, delete it there
                                     Try, try, try again until you succeed
I hated every minute of training, but I said, 'Don't quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali 
                              You may not be the best, but must be the most effort
     Even the things and people you like, you don't have the courage to take, you are destined to be a failure.
                                           Difficult means more time
                                         Pain + Reflection = Progress 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const ll mod = 1e9+7;

struct sparse_segment_tree  //luu y bo nho n.logn nen de toan cuc 
{
    struct node 
    {
        ll sum, lazy;
        node *leftchild, *rightchild;
    
        node()
        {
            sum=0;
            lazy=0;
            leftchild=rightchild=NULL;
        }
    
        ~node()
        {
            delete leftchild;
            delete rightchild;
        }
    };
    ll maxn;
    node *root=new node();

    sparse_segment_tree(){}
    sparse_segment_tree(ll _maxn)
    {
        maxn=_maxn;
    }
    
    void extend(node *root, ll l, ll r)
    {
        if (l!=r)
        {
            if (root->leftchild==NULL) root->leftchild=new node();
            if (root->rightchild==NULL) root->rightchild=new node();
        }
    }
    
    void down(node *root, ll l, ll r)
    {
        if (root->lazy!=0)
        {
            root->sum=(r-l+1)*root->lazy;
            if (l!=r)
            {
                extend(root, l, r);
                root->leftchild->lazy=root->lazy;
                root->rightchild->lazy=root->lazy;
            }   
            root->lazy=0;
        }
    }
    
    void update(node *root, ll l, ll r, ll u, ll v, ll val)
    {
        down(root, l, r);
        if (l>v || r<u || u>v) return;   
        if (u<=l && r<=v) 
        {
            root->lazy=val;
            down(root, l, r);   
            return;
        }
        extend(root, l, r);
        ll mid=(l+r)/2;
        update(root->leftchild, l, mid, u, v, val);
        update(root->rightchild, mid+1, r, u, v, val);
        root->sum = root->leftchild->sum + root->rightchild->sum;  
    }
    
    ll query(node *root, ll l, ll r, ll u, ll v)
    {
        down(root, l, r);
        if (l>v || r<u || u>v) return 0;
        if (u<=l && r<=v) return root->sum;
        extend(root, l, r);
        ll mid=(l+r)/2;
        return query(root->leftchild, l, mid, u, v) + query(root->rightchild, mid+1, r, u, v);
    }

    void update(ll u, ll v, ll val)
    {
        update(root, 1, maxn, u, v, val);
    }

    ll query(ll u, ll v)
    {
        return query(root, 1, maxn, u, v);
    }
};
sparse_segment_tree seg(1e9);

ll q, c;
void solve()
{
    cin>>q;
    while (q--)
    {
        ll type, l, r; cin>>type>>l>>r; l+=c; r+=c; assert(l<=1e9 && r<=1e9);
        if (type==1) c=seg.query(l, r), cout<<c<<endl;
        else seg.update(l, r, 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
    //#ifndef ONLINE_JUDGE
    //freopen("_input.txt", "r", stdin);
    //freopen("_output.txt", "w", stdout);
    //#endif
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 13 ms 8660 KB Output is correct
5 Correct 16 ms 10580 KB Output is correct
6 Correct 16 ms 10068 KB Output is correct
7 Correct 17 ms 10512 KB Output is correct
8 Correct 144 ms 77860 KB Output is correct
9 Correct 279 ms 132612 KB Output is correct
10 Correct 286 ms 148556 KB Output is correct
11 Correct 301 ms 161060 KB Output is correct
12 Correct 317 ms 166636 KB Output is correct
13 Correct 287 ms 207168 KB Output is correct
14 Correct 307 ms 209048 KB Output is correct
15 Runtime error 316 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -