Submission #523637

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523637	2022-02-08T02:30:22 Z	tmn2005	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	323 ms	121064 KB

apple

#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair
 
using namespace std;
 
typedef long long ll;
 
const int inf = (int)1e9 + 7;
const int N = (int)7e6 + 7e5;
 
int n;
int type,x,y,c;
int cnt = 1;
 
struct node {
        int l = 0,r = 0,sum = 0,add = 0;
        //node () {
                //l = r = add = sum = 0;
        //}
}t[N];
void push (int v,int tl,int tr) {
        if (t[v].add != 0) {
                if (!t[v].l)
                        t[v].l = ++cnt;
                if (!t[v].r)
                        t[v].r = ++cnt;
 
                t[t[v].l].add = t[v].add;
                t[t[v].r].add = t[v].add;
                t[v].sum = (tr - tl + 1);
        }
        t[v].add = 0;
}
void update (int l,int r,int v = 1,int tl = 1,int tr = 1e9 + 7) {
        if (tl > r || tr < l)
                return;
        if (t[v].add != 0)
                push (v,tl,tr);
 
        if (l <= tl && tr <= r) {
                t[v].add = 1;
        }
        else {
              int tm = (tl + tr) >> 1;
 
              if (t[v].l == 0)
                        t[v].l = ++cnt;
              if (t[v].r == 0)
                        t[v].r = ++cnt;
 
              update (l,r,t[v].l,tl,tm);
              update (l,r,t[v].r,tm + 1,tr);
 
              push (v,tl,tr);
              push (t[v].l,tl,tm);
              push (t[v].r,tm + 1,tr);
 
              t[v].sum = t[t[v].l].sum + t[t[v].r].sum;
        }
}
int get (int l,int r,int v = 1,int tl = 1,int tr = 1e9 + 7) {
        if (tl > r || tr < l)
                return 0;
        push (v,tl,tr);
 
        if (l <= tl && tr <= r)
                return t[v].sum;
 
        int tm = (tl + tr) >> 1;
 
        return get (l,r,t[v].l,tl,tm) + get(l,r,t[v].r,tm + 1,tr);
}
int main () {
        scanf ("%d", &n);
 
        for (int i = 1; i <= n; i ++) {
                scanf ("%d%d%d", &type,&x,&y);
                x += c;
                y += c;
 
                if (type == 1) {
                        c = get(x,y);
                        printf("%d\n", c);
                }
                else {
                        update (x,y);
                }
        }
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:79:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf ("%d", &n);
      |         ~~~~~~^~~~~~~~~~
apple.cpp:82:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |                 scanf ("%d%d%d", &type,&x,&y);
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	304 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	12 ms	3012 KB	Output is correct
5	Correct	15 ms	3636 KB	Output is correct
6	Correct	15 ms	3532 KB	Output is correct
7	Correct	15 ms	3632 KB	Output is correct
8	Correct	103 ms	26052 KB	Output is correct
9	Correct	234 ms	45252 KB	Output is correct
10	Correct	224 ms	49832 KB	Output is correct
11	Correct	241 ms	53784 KB	Output is correct
12	Correct	237 ms	55156 KB	Output is correct
13	Correct	214 ms	63836 KB	Output is correct
14	Correct	220 ms	64580 KB	Output is correct
15	Correct	294 ms	117672 KB	Output is correct
16	Correct	310 ms	118420 KB	Output is correct
17	Correct	218 ms	66628 KB	Output is correct
18	Correct	228 ms	66708 KB	Output is correct
19	Correct	304 ms	120992 KB	Output is correct
20	Correct	323 ms	121064 KB	Output is correct