Submission #673377

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
673377	2022-12-20T12:41:27 Z	smartmonky	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	657 ms	243112 KB

apple

#include <bits/stdc++.h>

#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
const int n = 1e9 + 5;
struct node{
    int sum = 0;
    short flag = 0;
    node *l, *r;
    node(){
        sum = 0, flag = 0;
        l = nullptr;
        r = nullptr;
    }
};
void push(node *&p,int l,int r){
	if(l != r && p ->flag){
		int mid = (l + r) >> 1;
		p -> l -> flag = 1;
		p -> r -> flag = 1;
		p -> l -> sum = (mid - l + 1);
		p -> r -> sum = (r - (mid + 1) + 1); 
	}
	p -> flag = 0;
}
void update(node *&p, int l, int r, int tl = 1, int tr = n){
    if(p == nullptr){
        p = new node();
    }
    if(tl > r || tr < l)
        return;
    if(tl >= l && tr <= r){
        p -> sum = (tr - tl + 1);
        p -> flag = 1;
        if(p -> l == nullptr)p -> l = new node();
		if(p -> r == nullptr)p -> r = new node();
        push(p, tl, tr);
        return;
    }
    int mid = (tl + tr) >> 1;
    if(p -> l == nullptr)p -> l = new node();
	if(p -> r == nullptr)p -> r = new node();
	update(p -> l, l, r, tl, mid);
	update(p -> r, l, r, mid + 1, tr);
    push(p, tl, tr);
    p -> sum = p -> l -> sum + p -> r -> sum;
}
int get(node *&p, int l, int r, int tl = 1, int tr = n){
	if(p == nullptr){
        p = new node();
    }
    if(p -> l == nullptr)p -> l = new node();
	if(p -> r == nullptr)p -> r = new node();
	push(p, tl, tr);
    if(tl > r || tr < l)
        return 0;
    if(tl >= l && tr <= r)
        return p -> sum;
    push(p, tl, tr);
    p -> sum = p -> l -> sum + p -> r -> sum;
    int mid = (tl + tr) >> 1;
    return get(p -> r, l, r, mid + 1, tr) + get(p -> l, l, r, tl, mid);
}

main(){
    node *root = new node();
    int n;
    cin >> n;
    int dob = 0;
    for(int i = 0; i < n; i++){
		int t, l, r;
		cin >> t >> l >> r;
		if(t == 2){
			update(root, l + dob, r + dob);
		}else{
			int ans = get(root, l + dob, r + dob);
			cout << ans <<  endl;
			dob = ans;
		}
	}
}

Compilation message

apple.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main(){
      | ^~~~
apple.cpp: In function 'void fp(std::string)':
apple.cpp:12:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:12:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	27 ms	5588 KB	Output is correct
5	Correct	32 ms	6828 KB	Output is correct
6	Correct	33 ms	6528 KB	Output is correct
7	Correct	35 ms	6776 KB	Output is correct
8	Correct	231 ms	51416 KB	Output is correct
9	Correct	418 ms	88928 KB	Output is correct
10	Correct	437 ms	98356 KB	Output is correct
11	Correct	496 ms	105600 KB	Output is correct
12	Correct	464 ms	109020 KB	Output is correct
13	Correct	428 ms	126524 KB	Output is correct
14	Correct	491 ms	127412 KB	Output is correct
15	Correct	652 ms	235756 KB	Output is correct
16	Correct	646 ms	237784 KB	Output is correct
17	Correct	445 ms	133796 KB	Output is correct
18	Correct	441 ms	133964 KB	Output is correct
19	Correct	657 ms	242928 KB	Output is correct
20	Correct	639 ms	243112 KB	Output is correct