Submission #483565

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
483565	2021-10-30T18:49:20 Z	Protostar	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	327 ms	203460 KB

apple

#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;
      |         ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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