답안 #771575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771575 2023-07-03T06:37:05 Z taitruong270 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
501 ms 262144 KB
/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
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
                                          Noi dau + Suy ngam = Tien bo 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
const ll mod = 1e9+7;

struct node 
{
    ll sum, lazy;
    node *leftchild, *rightchild;

    node()
    {
        sum=0;
        lazy=0;
        leftchild=rightchild=nullptr;
    }

    ~node()
    {
        delete leftchild;
        delete rightchild;
    }
};
node *root=new node();

void extend(node *root, ll l, ll r)
{
    if (l!=r)
    {
        if (root->leftchild==nullptr) root->leftchild=new node();
        if (root->rightchild==nullptr) 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);
}
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=query(root, 1, 1e9, l, r), cout<<c<<endl;
        else update(root, 1, 1e9, 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 13 ms 5828 KB Output is correct
5 Correct 21 ms 7056 KB Output is correct
6 Correct 17 ms 6712 KB Output is correct
7 Correct 17 ms 7028 KB Output is correct
8 Correct 124 ms 51488 KB Output is correct
9 Correct 251 ms 87360 KB Output is correct
10 Correct 270 ms 98068 KB Output is correct
11 Correct 299 ms 106464 KB Output is correct
12 Correct 277 ms 110056 KB Output is correct
13 Correct 267 ms 136940 KB Output is correct
14 Correct 316 ms 138212 KB Output is correct
15 Correct 501 ms 254576 KB Output is correct
16 Correct 464 ms 256476 KB Output is correct
17 Correct 272 ms 145328 KB Output is correct
18 Correct 302 ms 145356 KB Output is correct
19 Correct 448 ms 262144 KB Output is correct
20 Correct 455 ms 262144 KB Output is correct