Submission #483564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
483564	2021-10-30T18:47:24 Z	Protostar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	307 ms	205972 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(int, int, 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	46 ms	100388 KB	Output is correct
2	Correct	51 ms	100464 KB	Output is correct
3	Correct	45 ms	100420 KB	Output is correct
4	Correct	53 ms	100400 KB	Output is correct
5	Correct	56 ms	100504 KB	Output is correct
6	Correct	56 ms	100428 KB	Output is correct
7	Correct	56 ms	100504 KB	Output is correct
8	Correct	129 ms	100708 KB	Output is correct
9	Correct	215 ms	100844 KB	Output is correct
10	Correct	220 ms	100812 KB	Output is correct
11	Correct	226 ms	100864 KB	Output is correct
12	Correct	222 ms	100852 KB	Output is correct
13	Correct	202 ms	100956 KB	Output is correct
14	Correct	197 ms	100928 KB	Output is correct
15	Runtime error	307 ms	205972 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-