oj.uz

Submission #967969

# Submission time Handle Problem Language Result Execution time Memory
967969 2024-04-23T06:12:38 Z hasan2006 Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 426 ms 204696 KB 
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 1e7 + 9 , mod = 1e9 + 7;
ll t[N] , lz[N] , cnt = 1 , L[N] , R[N];

void pushup(int i){
    t[i] = t[L[i]] + t[R[i]];
}

void pushlazy(int i ,ll l , ll r){
    if(!i || l == r || !lz[i])
        return;
    ll m = (l + r) / 2;
    if(!L[i]) L[i] = ++cnt;
    if(!R[i]) R[i] = ++cnt;
    t[L[i]] = (m - l + 1) * lz[i];
    t[R[i]] = (r - m) * lz[i];
    lz[R[i]] = lz[L[i]] = 1;
    lz[i] = 0;
}

void add(int i , ll l , ll r , ll tl , ll tr){
    ll m = (l + r) / 2;
    if(l > r || l > tr || r < tl || !i) return;
    pushlazy(i , l , r);
    if(l >= tl && r <= tr){
        t[i] = (r -  l + 1) ;
        lz[i] = 1;
    }else {
        if(tl <= m){
            if(!L[i])
                L[i] = ++cnt;
            add(L[i] , l , m , tl , tr );
        }
        if(tr > m){
            if(!R[i])
                R[i] = ++cnt;
            add(R[i] , m + 1 , r , tl , tr );
        }
        pushup(i);
    }
}

ll get(int i , ll l , ll r , ll tl , ll tr){
    ll m = (l + r) / 2;
    if(l > r || l > tr || r < tl || !i) return 0;
    pushlazy(i , l,  r);
    if(l >= tl && r <= tr){
        return t[i];
    }else {
        return get(L[i] , l , m , tl , tr) + get(R[i] , m + 1 , r , tl , tr);
    }
}

void solve()
{
    ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
    cin>>q;
    while(q--){
        cin>>k>>l>>r;
        if(k == 1){
            s = get(1 , -1e12 , 1e12 , l + s , r + s);
            cout<<s<<"\n";
        }else{
            add(1 , -1e12 , 1e12 , l + s , r  + s);
        }
    }
}

int main(){
 /*   TL;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    int t = 1;
//    cin>>t;
    while(t--)
     {
        solve();
     }
}
// Author : حسن

Compilation message

apple.cpp: In function 'void solve()':
apple.cpp:75:8: warning: unused variable 'n' [-Wunused-variable]
   75 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |        ^
apple.cpp:75:16: warning: unused variable 'i' [-Wunused-variable]
   75 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                ^
apple.cpp:75:20: warning: unused variable 'j' [-Wunused-variable]
   75 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                    ^
apple.cpp:75:30: warning: unused variable 'x' [-Wunused-variable]
   75 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                              ^
apple.cpp:75:34: warning: unused variable 'y' [-Wunused-variable]
   75 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                  ^
apple.cpp:75:46: warning: unused variable 'f' [-Wunused-variable]
   75 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                              ^
apple.cpp:75:54: warning: unused variable 'm' [-Wunused-variable]
   75 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                      ^
apple.cpp:75:58: warning: unused variable 'mx' [-Wunused-variable]
   75 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                          ^~
apple.cpp:75:67: warning: unused variable 'mn' [-Wunused-variable]
   75 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                                   ^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 17 ms 5724 KB Output is correct
5 Correct 22 ms 6236 KB Output is correct
6 Correct 22 ms 6288 KB Output is correct
7 Correct 22 ms 6224 KB Output is correct
8 Correct 152 ms 44884 KB Output is correct
9 Correct 330 ms 71840 KB Output is correct
10 Correct 362 ms 81624 KB Output is correct
11 Correct 354 ms 89164 KB Output is correct
12 Correct 357 ms 90340 KB Output is correct
13 Correct 307 ms 110132 KB Output is correct
14 Correct 307 ms 112584 KB Output is correct
15 Correct 426 ms 197716 KB Output is correct
16 Correct 418 ms 200276 KB Output is correct
17 Correct 301 ms 114484 KB Output is correct
18 Correct 304 ms 114584 KB Output is correct
19 Correct 424 ms 204696 KB Output is correct
20 Correct 410 ms 204628 KB Output is correct