oj.uz

Submission #671670

# Submission time Handle Problem Language Result Execution time Memory
671670 2022-12-13T12:47:53 Z tolbi Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 509 ms 240428 KB 
    #pragma optimize("Bismillahirrahmanirrahim")
    //█▀█─█──█──█▀█─█─█
    //█▄█─█──█──█▄█─█■█
    //█─█─█▄─█▄─█─█─█─█
    //Allahuekber
    //ahmet23 orz...
    //Sani buyuk Osman Pasa Plevneden cikmam diyor.
    //FatihSultanMehmedHan
    //YavuzSultanSelimHan
    //AbdulhamidHan
    #define author tolbi
    #include <bits/stdc++.h>
    #define endl '\n'
    #define vint(x) vector<int> x
    #define deci(x) int x;cin>>x;
    #define decstr(x) string x;cin>>x;
    #define cinarr(x) for (auto &it : x) cin>>it;
    #define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
    #define sortarr(x) sort(x.begin(),x.end())
    #define sortrarr(x) sort(x.rbegin(),x.rend())
    #define det(x) cout<<"NO\0YES"+x*3<<endl;
    #define INF LONG_LONG_MAX
    #define rev(x) reverse(x.begin(),x.end());
    #define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
using namespace std;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
struct Node{
	int val, lnode, rnode, l, r, lazy;
	Node():lnode(-1),rnode(-1),val(0),lazy(0){}
};
vector<Node> segtree;
void lyap(int node){
	int mid = segtree[node].l+(segtree[node].r-segtree[node].l)/2;
	if (segtree[node].lnode==-1){
		segtree[node].lnode=segtree.size();
		segtree.push_back(Node());
		segtree[segtree[node].lnode].l=segtree[node].l;
		segtree[segtree[node].lnode].r=mid;
	}
}
void ryap(int node){
	int mid = segtree[node].l+(segtree[node].r-segtree[node].l)/2;
	if (segtree[node].rnode==-1){
		segtree[node].rnode=segtree.size();
		segtree.push_back(Node());
		segtree[segtree[node].rnode].l=mid+1;
		segtree[segtree[node].rnode].r=segtree[node].r;
	}
}
void dallan(int node){
	if (segtree[node].lazy==1){
		lyap(node);
		ryap(node);
		segtree[segtree[node].lnode].lazy=1;
		segtree[segtree[node].rnode].lazy=1;
		segtree[node].val=segtree[node].r-segtree[node].l+1;
	}
	segtree[node].lazy=0;
}
int query(int l, int r, int node = 0){
	dallan(node);
	if (segtree[node].l>=l && segtree[node].r<=r) return segtree[node].val;
	if (segtree[node].l>r || segtree[node].r<l) return 0ll;
	int rval = 0;
	if (segtree[node].lnode!=-1){
		rval+=query(l, r, segtree[node].lnode);
	}
	if (segtree[node].rnode!=-1){
		rval+=query(l, r, segtree[node].rnode);
	}
	return rval;
}
void update(int l, int r, int node = 0) {
	dallan(node);
	if (segtree[node].l>=l && segtree[node].r<=r){
		segtree[node].lazy=1;
		dallan(node);
		return;
	}
	if (segtree[node].l>r || segtree[node].r<l) return;
	int mid = segtree[node].l+(segtree[node].r-segtree[node].l)/2;
	if (mid>=l){
		lyap(node);
		update(l, r, segtree[node].lnode);
	}
	if (mid+1<=r){
		ryap(node);
		update(l, r, segtree[node].rnode);
	}
	segtree[node].val=0ll;
	if (segtree[node].lnode!=-1){
		dallan(segtree[node].lnode);
		segtree[node].val+=segtree[segtree[node].lnode].val;
	}
	if (segtree[node].rnode!=-1){
		dallan(segtree[node].rnode);
		segtree[node].val+=segtree[segtree[node].rnode].val;
	}
}
int32_t main(){
	ios;
	int t=1;
	int tno = 0;
	if (!t) cin>>t;
	while (t-(tno++)){
		segtree.push_back(Node());
		segtree[0].l=1;
		segtree[0].r=1000000000;
		segtree[0].val=0;
		segtree[0].lazy=0;
		deci(q);
		int c = 0;
		while (q--){
			assert(segtree.size()<=5000000);
			deci(d);
			deci(l);deci(r);
			l+=c;
			r+=c;
			if (d==1){
				c=query(l,r);
				cout<<c<<endl;
			}
			else {
				update(l,r);
			}
		}
	}
}

Compilation message

apple.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 |     #pragma optimize("Bismillahirrahmanirrahim")
      | 
apple.cpp: In constructor 'Node::Node()':
apple.cpp:30:18: warning: 'Node::rnode' will be initialized after [-Wreorder]
   30 |  int val, lnode, rnode, l, r, lazy;
      |                  ^~~~~
apple.cpp:30:6: warning:   'int Node::val' [-Wreorder]
   30 |  int val, lnode, rnode, l, r, lazy;
      |      ^~~
apple.cpp:31:2: warning:   when initialized here [-Wreorder]
   31 |  Node():lnode(-1),rnode(-1),val(0),lazy(0){}
      |  ^~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 22 ms 6664 KB Output is correct
5 Correct 26 ms 6600 KB Output is correct
6 Correct 27 ms 6548 KB Output is correct
7 Correct 26 ms 6596 KB Output is correct
8 Correct 192 ms 49720 KB Output is correct
9 Correct 403 ms 99088 KB Output is correct
10 Correct 413 ms 99144 KB Output is correct
11 Correct 419 ms 99088 KB Output is correct
12 Correct 426 ms 99116 KB Output is correct
13 Correct 449 ms 198020 KB Output is correct
14 Correct 445 ms 197896 KB Output is correct
15 Runtime error 509 ms 240428 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -