답안 #483565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483565 2021-10-30T18:49:20 Z Protostar 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
327 ms 203460 KB
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")

typedef long long ll;
typedef long double ld;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define Confundo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define minheap priority_queue<int,vector<int>,greater<int>>
#define print2d(dp,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
#define ftt int t;cin>>t;for(int tt=1;tt<=t;++tt)
#define Sum(v) accumulate(v.begin(),v.end(),(ll)0)
#define Rev(v) reverse(v.begin(),v.end());
#define Sort(v) sort(v.begin(),v.end());
#define Input(v) for(auto &x:v) cin>>x;
#define Output(v) for(auto x:v) cout<<x<<" ";
#define mem(a, b) memset(a, b, sizeof(a))
#define dbgx(x) cout<<"\nhi "<<x<<"\n"
#define double long double
// #define int long long
#define maxheap priority_queue<int>
#define dbg cout<<"\nhi\n"
#define sayy cout<<"YES\n"
#define sayn cout<<"NO\n"
#define pii pair<int,int>
#define mii map<int,int>
#define umii unordered_map<int,int>
#define vii vector<pair<int,int>>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vi vector<int>
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define snd second
#define fst first
#define endl "\n"

const int INF    = numeric_limits<int>::max() / 2;
const double PI  = 3.1415926535898;
const int MOD    = 1e9 + 7;
const int LIM    = 128 * 1e5 + 5;

// O(log y)
int fpow(int x, int y) {
    int temp;
    if (y == 0)
        return 1;
    temp = fpow(x, y / 2);
    if (y % 2 == 0)
        return (temp * temp) % MOD;
    else
        return (x * ((temp * temp) % MOD)) % MOD;
}

// O(log max(a, b))
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

struct node
{
    int l, r, val, lazy;

    node()
    {
        val = lazy = l = r = 0;
    }
};

int numNodes;
node segmentTree[LIM];

void lazyPropagate(int index, int l, int r)
{
    if (segmentTree[index].lazy == 0)
        return;

    segmentTree[index].val = r - l + 1;

    int mid = l + (r - l) / 2;

    if (segmentTree[index].l == 0)
        segmentTree[index].l = ++numNodes;

    if (segmentTree[index].r == 0)
        segmentTree[index].r = ++numNodes;

    segmentTree[segmentTree[index].l].lazy =
        segmentTree[segmentTree[index].r].lazy = 1;

    segmentTree[index].lazy = 0;
}

int update(int index, int curL, int curR, int queryL, int queryR)
{
    if (index == 0)
        index = ++numNodes;

    lazyPropagate(index, curL, curR);

    if (queryR < curL || queryL > curR)
        return index;

    if (queryL <= curL && queryR >= curR)
    {
        segmentTree[index].lazy = 1;
        lazyPropagate(index, curL, curR);
        return index;
    }

    int mid = (curL + curR) / 2;

    segmentTree[index].l = update(segmentTree[index].l, curL, mid, queryL, queryR);
    segmentTree[index].r = update(segmentTree[index].r, mid + 1, curR, queryL, queryR);

    segmentTree[index].val = segmentTree[segmentTree[index].l].val +
                             segmentTree[segmentTree[index].r].val;

    return index;
}

int query(int index, int curL, int curR, int queryL, int queryR)
{
    if (queryR < curL || queryL > curR || index == 0)
        return 0;

    lazyPropagate(index, curL, curR);

    if (queryL <= curL && queryR >= curR)
        return segmentTree[index].val;

    int mid = (curL + curR) / 2;

    return query(segmentTree[index].l, curL, mid, queryL, queryR) +
           query(segmentTree[index].r, mid + 1, curR, queryL, queryR);
}

void solve()
{
    int m, c = 0;
    cin >> m;

    numNodes = 1;

    for (int i = 0; i < m; ++i)
    {
        int d, x, y;
        cin >> d >> x >> y;

        if (d == 1)
        {
            c = query(1, 1, 1e9, x + c, y + c);
            cout << c << endl;
        }
        else
        {
            update(1, 1, 1e9, x + c, y + c);
        }
    }

    return;
}


//*************************************************************************************************************************


int32_t main()
{
    Confundo;

    // ftt
    {
        solve();
    }

    return 0;
}

Compilation message

apple.cpp: In function 'void lazyPropagate(int, int, int)':
apple.cpp:94:9: warning: unused variable 'mid' [-Wunused-variable]
   94 |     int mid = l + (r - l) / 2;
      |         ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 200640 KB Output is correct
2 Correct 88 ms 200636 KB Output is correct
3 Correct 88 ms 200564 KB Output is correct
4 Correct 99 ms 200636 KB Output is correct
5 Correct 109 ms 200640 KB Output is correct
6 Correct 100 ms 200632 KB Output is correct
7 Correct 98 ms 200600 KB Output is correct
8 Correct 164 ms 200752 KB Output is correct
9 Correct 258 ms 200952 KB Output is correct
10 Correct 265 ms 200944 KB Output is correct
11 Correct 270 ms 201284 KB Output is correct
12 Correct 270 ms 201032 KB Output is correct
13 Correct 245 ms 201068 KB Output is correct
14 Correct 250 ms 201156 KB Output is correct
15 Correct 327 ms 201192 KB Output is correct
16 Correct 316 ms 203460 KB Output is correct
17 Correct 245 ms 203168 KB Output is correct
18 Correct 253 ms 203228 KB Output is correct
19 Correct 315 ms 203332 KB Output is correct
20 Correct 319 ms 203344 KB Output is correct