Submission #483562

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
483562	2021-10-30T18:41:52 Z	Protostar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	351 ms	205748 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    = 32 * 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	52 ms	100444 KB	Output is correct
2	Correct	48 ms	100476 KB	Output is correct
3	Correct	45 ms	100388 KB	Output is correct
4	Correct	53 ms	100524 KB	Output is correct
5	Correct	56 ms	100636 KB	Output is correct
6	Correct	78 ms	100676 KB	Output is correct
7	Correct	59 ms	100576 KB	Output is correct
8	Correct	129 ms	101508 KB	Output is correct
9	Correct	262 ms	102556 KB	Output is correct
10	Correct	269 ms	102596 KB	Output is correct
11	Runtime error	351 ms	205748 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-