Submission #483563

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
483563	2021-10-30T18:44:33 Z	Protostar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	525 ms	262144 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    = 64 * 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(long long int, long long int, long long int)':
apple.cpp:94:9: warning: unused variable 'mid' [-Wunused-variable]
   94 |     int mid = l + (r - l) / 2;
      |         ^~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	200644 KB	Output is correct
2	Correct	91 ms	200588 KB	Output is correct
3	Correct	88 ms	200604 KB	Output is correct
4	Correct	104 ms	200644 KB	Output is correct
5	Correct	100 ms	200656 KB	Output is correct
6	Correct	106 ms	200656 KB	Output is correct
7	Correct	98 ms	200660 KB	Output is correct
8	Correct	184 ms	200816 KB	Output is correct
9	Correct	297 ms	200964 KB	Output is correct
10	Correct	299 ms	201048 KB	Output is correct
11	Correct	300 ms	201064 KB	Output is correct
12	Correct	352 ms	202860 KB	Output is correct
13	Correct	251 ms	203156 KB	Output is correct
14	Correct	299 ms	203148 KB	Output is correct
15	Runtime error	525 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-