oj.uz

답안 #1098756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1098756 2024-10-09T20:46:04 Z SSSM 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 466 ms 219696 KB 
#include <bits/stdc++.h>

/*
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
*/

using namespace std;

/*
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define F first
#define S second
#define pb push_back
#define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
#define md(a) (a%mod+mod)%mod
#define all(a) a.begin(), a.end()
#define MP make_pair
#define lc id<<1
#define rc lc|1
#define mid (l+r)/2
#define kill(a) cout << a << "\n", exit(0)
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
mt19937_64  rng(chrono::steady_clock::now().time_since_epoch().count());

ll const maxn=1e5+10, mod=1e9+7, INF=1e18, LOG=60, sq=1e3;

ll poww(ll a, ll b, ll mod) {
 if (b == 0) return 1;
 return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod;
}

ll n;
vector<ll> seg, lz;
vector<pll> ch;

void Make(ll l, ll r, ll id)
{
    ch[id].F=ch.size();
    ch.pb({-1, -1});
    seg.pb(0);
    lz.pb(-1);
    ch[id].S=ch.size();
    ch.pb({-1, -1});
    seg.pb(0);
    lz.pb(-1);
}

void Modify(ll l, ll r, ll id, ll x)
{
    lz[id]=x;
    seg[id]=(r-l)*x;
}

void Shift(ll l, ll r, ll id)
{
    if(ch[id].F==-1) Make(l, r, id);
    if(lz[id]!=-1 && r-l>1)
    {
        Modify(l, mid, ch[id].F, lz[id]);
        Modify(mid, r, ch[id].S, lz[id]);
        //cout<<id<<"***\n";
        lz[id]=-1;
    }
}

void Upd(ll s, ll e, ll x, ll l=1, ll r=mod, ll id=0)
{
   // cout<<id<<"+++\n";
    if(l>=e || r<=s) return;
    if(s<=l && r<=e){
        Modify(l, r, id, x);
        return;
    }
    Shift(l, r, id);
    Upd(s, e, x, l, mid, ch[id].F);
    Upd(s, e, x, mid, r, ch[id].S);
    seg[id]=seg[ch[id].F]+seg[ch[id].S];
}

ll Get(ll s, ll e, ll l=1, ll r=mod, ll id=0)
{
    if(l>=e || r<=s) return 0;
    if(s<=l && r<=e) return seg[id];
    Shift(l, r, id);
    return Get(s, e, l, mid, ch[id].F)+Get(s, e, mid, r, ch[id].S);
}

int main() {
    
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n;
    ll c=0;

    seg.pb(0);
    lz.pb(-1);
    ch.pb({-1, -1});
    while(n--)
    {
        ll t, l, r;
        cin>>t>>l>>r;
        l+=c;
        r+=c+1;
        if(t==1)
        {
           ll ans=Get(l, r);
           c=ans;
           cout<<ans<<"\n";
        }
        else
        {
            Upd(l, r, 1);
        }
    }

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 16 ms 4808 KB Output is correct
5 Correct 19 ms 5580 KB Output is correct
6 Correct 19 ms 5324 KB Output is correct
7 Correct 19 ms 5576 KB Output is correct
8 Correct 124 ms 35924 KB Output is correct
9 Correct 278 ms 72568 KB Output is correct
10 Correct 273 ms 77960 KB Output is correct
11 Correct 290 ms 82292 KB Output is correct
12 Correct 297 ms 84012 KB Output is correct
13 Correct 318 ms 121300 KB Output is correct
14 Correct 315 ms 121200 KB Output is correct
15 Correct 446 ms 219692 KB Output is correct
16 Correct 466 ms 219696 KB Output is correct
17 Correct 316 ms 121316 KB Output is correct
18 Correct 327 ms 121200 KB Output is correct
19 Correct 427 ms 219692 KB Output is correct
20 Correct 415 ms 219628 KB Output is correct