oj.uz

Submission #671654

# Submission time Handle Problem Language Result Execution time Memory
671654 2022-12-13T12:21:44 Z tolbi Colors (BOI20_colors) C++17
0 / 100
 1 ms 208 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 int long long
#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 SegTree{
	struct Node{
		int val, lnode, rnode, l, r, lazy;
		Node():lnode(-1),rnode(-1),val(0),lazy(0){}
	};
	vector<Node> segtree;
	SegTree(){
		segtree.push_back(Node());
		segtree[0].l=1;
		segtree[0].r=1000000000;
		segtree[0].val=0;
		segtree[0].lazy=0;
	}
	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){
			segtree[node].val+=segtree[segtree[node].lnode].val;
		}
		if (segtree[node].rnode!=-1){
			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 segtree;
		deci(q);
		int c = 0;
		while (q--){
			deci(d);
			deci(l);deci(r);
			l+=c;
			r+=c;
			if (d==1){
				c=segtree.query(l,r);
				cout<<c<<endl;
			}
			else {
				segtree.update(l,r);
			}
		}
	}
}

Compilation message

Colors.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
Colors.cpp: In constructor 'SegTree::Node::Node()':
Colors.cpp:32:19: warning: 'SegTree::Node::rnode' will be initialized after [-Wreorder]
   32 |   int val, lnode, rnode, l, r, lazy;
      |                   ^~~~~
Colors.cpp:32:7: warning:   'long long int SegTree::Node::val' [-Wreorder]
   32 |   int val, lnode, rnode, l, r, lazy;
      |       ^~~
Colors.cpp:33:3: warning:   when initialized here [-Wreorder]
   33 |   Node():lnode(-1),rnode(-1),val(0),lazy(0){}
      |   ^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -