Submission #1001034

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1001034	2024-06-18T13:14:43 Z	LilPluton	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	393 ms	262144 KB

apple

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
/// author: LilPluton auuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
#define OPT         ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int         ll
#define ll          long long
#define pb          push_back
#define arr         array
#define vll         vector<int>
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
#define fi          first
#define se          second
#define rep(i,j,k)  for(int i = j; i <= k; ++i)
#define all(a)      a.begin(),a.end()
#define pii         pair<int,int>
#define endll       '\n'
using namespace std;

const int sz = (6e6 + 100);
const int N = 1e9;
int t[sz * 4], L[sz * 4], R[sz * 4], nxt = 1, lz[sz * 4];

void init(int node,int l,int r)
{
    if(lz[node])
    {
        t[node] = r - l + 1;
        if(l != r){
            if(!L[node]) L[node] = ++nxt;
            if(!R[node]) R[node] = ++nxt;
            lz[L[node]] = 1; 
            lz[R[node]] = 1;
        }
        lz[node] = 0;
    }
}

void upd(int node,int l,int r,int ql,int qr)
{
    init(node,l,r);
    if(ql > r || qr < l)
        return;
    if(ql <= l && r <= qr)
    {
        t[node] = r - l + 1;
        if(l != r){
            if(!L[node]) L[node] = ++nxt;
            if(!R[node]) R[node] = ++nxt;
            lz[L[node]] = 1; 
            lz[R[node]] = 1;
        }
        return;
    }
    ll mid = (l + r) >> 1;
    if(!L[node]) L[node]= ++nxt;
    upd(L[node], l, mid, ql, qr);
    if(!R[node]) R[node] = ++nxt;
    upd(R[node], mid + 1, r, ql, qr);
    t[node] = t[L[node]]+t[R[node]];
}

int getans(int node, int l,int r,int ql,int qr)
{
    init(node,l,r);
    if(ql > r || qr < l)    return 0;
    if(ql <= l && r <= qr)  return t[node];
    int mid = (l + r) >> 1;
    int q1, q2;
    if(L[node])
        q1 = getans(L[node],l,mid,ql,qr);
    else
        q1 = 0;
    if(R[node])
        q2 = getans(R[node], mid + 1, r, ql,qr);
    else
        q2 = 0;
    return q1 + q2;
}

signed main() {
    OPT
    int m;
    cin >> m;
    int c = 0;
    while(m--)
    {
        int t,a,b;
        cin >> t >> a >> b;
        a += c;
        b += c;
        if(t == 2)
            upd(1,1,N,a,b);
        else
        {
            int ans = getans(1,1,N,a,b);
            cout << ans << endl;
            c = ans;
        }

    }
}

Compilation message

apple.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization("unroll-loops")
      |

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	14 ms	9572 KB	Output is correct
5	Correct	17 ms	10332 KB	Output is correct
6	Correct	15 ms	10076 KB	Output is correct
7	Correct	17 ms	10088 KB	Output is correct
8	Correct	110 ms	53680 KB	Output is correct
9	Correct	247 ms	90448 KB	Output is correct
10	Correct	254 ms	101200 KB	Output is correct
11	Correct	249 ms	109380 KB	Output is correct
12	Correct	266 ms	113232 KB	Output is correct
13	Correct	229 ms	140376 KB	Output is correct
14	Correct	230 ms	141648 KB	Output is correct
15	Correct	393 ms	255828 KB	Output is correct
16	Correct	330 ms	257620 KB	Output is correct
17	Correct	233 ms	146512 KB	Output is correct
18	Correct	226 ms	146636 KB	Output is correct
19	Correct	377 ms	262144 KB	Output is correct
20	Correct	340 ms	262144 KB	Output is correct