답안 #771559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
771559	2023-07-03T06:26:59 Z	taitruong270	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	367 ms	262144 KB

apple

/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        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 l, r, sum, lazy;
    node *leftchild, *rightchild;

    node(ll _l, ll _r)
    {
        l=_l;
        r=_r;
        sum=0;
        lazy=0;
        leftchild=rightchild=nullptr;
    }

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

void extend(node *root)
{
    if (root->leftchild==nullptr && root->l!=root->r)
    {
        ll mid=(root->l+root->r)/2;
        if (root->leftchild==nullptr) root->leftchild=new node(root->l, mid);
        if (root->rightchild==nullptr) root->rightchild=new node(mid+1, root->r);
    }
}

void down(node *root)
{
    if (root->lazy!=0)
    {
        root->sum=(root->r-root->l+1)*root->lazy;
        if (root->l!=root->r)
        {
            extend(root);
            root->leftchild->lazy=root->lazy;
            root->rightchild->lazy=root->lazy;
        }   
        root->lazy=0;
    }
}

void update(node *root, ll u, ll v, ll val)
{
    down(root);
    if (root->l>v || root->r<u || u>v) return;   
    if (u<=root->l && root->r<=v) 
    {
        root->lazy=val;
        down(root);   
        return;
    }
    extend(root);
    update(root->leftchild, u, v, val);
    update(root->rightchild, u, v, val);
    root->sum = root->leftchild->sum + root->rightchild->sum;  
}

ll query(node *root, ll u, ll v)
{
    down(root);
    if (root->l>v || root->r<u || u>v) return 0;
    if (u<=root->l && root->r<=v) return root->sum;
    extend(root);
    return query(root->leftchild, u, v) + query(root->rightchild, 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, l, r), cout<<c<<endl;
        else update(root, l, r, 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
    
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	13 ms	8584 KB	Output is correct
5	Correct	17 ms	10324 KB	Output is correct
6	Correct	23 ms	9992 KB	Output is correct
7	Correct	17 ms	10324 KB	Output is correct
8	Correct	144 ms	77040 KB	Output is correct
9	Correct	306 ms	130816 KB	Output is correct
10	Correct	325 ms	146884 KB	Output is correct
11	Correct	341 ms	159300 KB	Output is correct
12	Correct	341 ms	164896 KB	Output is correct
13	Correct	327 ms	204988 KB	Output is correct
14	Correct	324 ms	206956 KB	Output is correct
15	Runtime error	367 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-