oj.uz

Submission #706413

# Submission time Handle Problem Language Result Execution time Memory
706413 2023-03-06T13:41:25 Z damwuan Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 275 ms 203540 KB 

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e5+69;
const ll inf=1e18;
const ll mod=1e9+7;
int n;
struct Tnode
{
    int l,r,val,lazy;
    Tnode(): l(-1),r(-1),val(0),lazy(0){};
}st[maxn*64];
int CntNode=1;
void addchild(int id)
{
    st[id].l=++CntNode;
    st[id].r=++CntNode;
}
void push(int id,int l,int mid,int r)
{
    int& t=st[id].lazy;
    if (t==0) return;
    st[st[id].l].lazy=t;
    st[st[id].r].lazy=t;
    st[st[id].l].val=t*(mid-l+1);
    st[st[id].r].val=t*(r-mid);
    t=0;
}
void Update(int id,int l,int r,int u,int v,int val)
{
    if (l>v || r<u)
    {
        return;
    }
    if (u<=l && r<=v)
    {
        st[id].val=(r-l+1)*val;
        st[id].lazy=val;
        return;
    }
    if (st[id].l==-1) addchild(id);

    int mid = l+r>>1;
    push(id,l,mid,r);
    Update(st[id].l,l,mid,u,v,val);
    Update(st[id].r,mid+1,r,u,v,val);
    st[id].val=st[st[id].l].val + st[st[id].r].val;
}
ll Get(int id,int l,int r,int u,int v)
{
    if (l>v || r<u)
    {
        return 0;
    }
    if (u<=l && r<=v)
    {
        return st[id].val;
    }
    if (st[id].l==-1) addchild(id);

    int mid = l+r>>1;
     push(id,l,mid,r);
    return Get(st[id].l,l,mid,u,v) + Get(st[id].r,mid+1,r,u,v);

}
void sol()
{
    cin >> n;
    int c=0;
    for (int i=1;i<=n;i++)
    {
        int type,l,r;cin >> type>>l>>r;
        l+=c;
        r+=c;
        if (type ==2) Update(1,1,1e9,l,r,1);
        else cout << (c=Get(1,1,1e9,l,r))<<'\n';
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sol();
}

Compilation message

apple.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int, long long int)':
apple.cpp:57:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = l+r>>1;
      |               ~^~
apple.cpp: In function 'll Get(long long int, long long int, long long int, long long int, long long int)':
apple.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = l+r>>1;
      |               ~^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 200780 KB Output is correct
2 Correct 78 ms 200736 KB Output is correct
3 Correct 78 ms 200760 KB Output is correct
4 Correct 88 ms 200960 KB Output is correct
5 Correct 87 ms 200944 KB Output is correct
6 Correct 90 ms 200904 KB Output is correct
7 Correct 91 ms 200908 KB Output is correct
8 Correct 142 ms 201856 KB Output is correct
9 Correct 217 ms 202852 KB Output is correct
10 Correct 233 ms 202944 KB Output is correct
11 Correct 218 ms 203000 KB Output is correct
12 Correct 219 ms 202948 KB Output is correct
13 Correct 202 ms 203340 KB Output is correct
14 Correct 202 ms 203372 KB Output is correct
15 Correct 246 ms 203460 KB Output is correct
16 Correct 260 ms 203540 KB Output is correct
17 Correct 220 ms 203420 KB Output is correct
18 Correct 220 ms 203400 KB Output is correct
19 Correct 249 ms 203480 KB Output is correct
20 Correct 275 ms 203452 KB Output is correct