oj.uz

Submission #386794

# Submission time Handle Problem Language Result Execution time Memory
386794 2021-04-07T10:11:57 Z nathanlee726 Food Court (JOI21_foodcourt) C++14
7 / 100
 153 ms 146496 KB 
//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int n,m,q;
struct segment_tree{
	struct NODE{
		vector<pii> ve;
		queue<pii> tg;
		int mi,v,tt;
		NODE():mi(0),v(0),tt(0){}
		int bs(int l,int r,int vl){
			if(l==r){
				return ve[l].Y;
			}
			int mi=(l+r)/2;
			bug(mi,ve[mi].X,vl);
			if(ve[mi].X>=vl)return bs(l,mi,vl);
			else return bs(mi+1,r,vl);
		}
	}seg[100010];
	void push(int p){
		while(!seg[p].tg.empty()){
			if(seg[p].tg.front().Y==-1){
				seg[p*2].mi=min(seg[p*2].v,seg[p*2].mi+seg[p].tg.front().X);
				seg[p*2+1].mi=min(seg[p*2+1].v,seg[p*2+1].mi+seg[p].tg.front().X);
				bug(p*2+1,seg[p*2+1].mi,seg[p].tg.front().X);
			}
			else{
				seg[p*2].v+=seg[p].tg.front().X;
				seg[p*2].ve.pb({seg[p*2].v,seg[p].tg.front().Y});
				seg[p*2+1].v+=seg[p].tg.front().X;
				seg[p*2+1].ve.pb({seg[p*2+1].v,seg[p].tg.front().Y});
			}
			seg[p*2].tg.push(seg[p].tg.front());
			seg[p*2+1].tg.push(seg[p].tg.front());
			seg[p].tg.pop();
		}
	}
	void insert(int p,int l,int r,int ql,int qr,pii vl){
		if(l>qr||r<ql)return;
		if(l>=ql&&r<=qr){
			seg[p].v+=vl.X;
			seg[p].ve.pb({seg[p].v,vl.Y});
			seg[p].tg.push(vl);
			return;
		}
		int mi=(l+r)/2;
		push(p);
		insert(p*2,l,mi,ql,qr,vl);
		insert(p*2+1,mi+1,r,ql,qr,vl);
		return;
	}
	void erase(int p,int l,int r,int ql,int qr,int vl){
		if(l>qr||r<ql)return;
		if(l>=ql&&r<=qr){
			seg[p].mi=min(seg[p].v,seg[p].mi+vl);
			bug(seg[p].mi,seg[p].v);
			seg[p].tg.push({vl,-1});
			return;
		}
		int mi=(l+r)/2;
		push(p);
		erase(p*2,l,mi,ql,qr,vl);
		erase(p*2+1,mi+1,r,ql,qr,vl);
		return;
	}
	int qry(int p,int l,int r,int x,int vl){
		if(l==r){
			bug(p,seg[p].mi,vl,seg[p].v,sz(seg[p].ve)-1);
			if(seg[p].mi+vl>seg[p].v)return 0;
			else return seg[p].bs(0,sz(seg[p].ve)-1,seg[p].mi+vl);
		}
		int mi=(l+r)/2;
		push(p);
		if(mi>=x)return qry(p*2,l,mi,x,vl);
		else return qry(p*2+1,mi+1,r,x,vl);
	}
}sgt;
signed main(){
	IOS();
	cin>>n>>m>>q;
	while(q--){
		int ty;
		cin>>ty;
		if(ty==1){
			int l,r,c,k;
			cin>>l>>r>>c>>k;
			--l,--r;
			sgt.insert(1,0,n-1,l,r,{k,c});
		}
		else if(ty==2){
			int l,r,k;
			cin>>l>>r>>k;
			--l,--r;
			sgt.erase(1,0,n-1,l,r,k);
		} 
		else{
			int x,y;
			cin>>x>>y;
			--x;
			cout<<sgt.qry(1,0,n-1,x,y)<<endl;
		}
	}
	return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 86636 KB Output is correct
2 Correct 112 ms 98796 KB Output is correct
3 Correct 102 ms 99436 KB Output is correct
4 Correct 122 ms 119404 KB Output is correct
5 Correct 59 ms 72428 KB Output is correct
6 Correct 60 ms 72396 KB Output is correct
7 Correct 122 ms 117996 KB Output is correct
8 Correct 126 ms 114152 KB Output is correct
9 Correct 119 ms 113388 KB Output is correct
10 Correct 119 ms 116204 KB Output is correct
11 Correct 121 ms 115308 KB Output is correct
12 Correct 121 ms 113152 KB Output is correct
13 Correct 98 ms 103916 KB Output is correct
14 Correct 112 ms 118252 KB Output is correct
15 Correct 91 ms 98796 KB Output is correct
16 Correct 128 ms 120684 KB Output is correct
17 Correct 94 ms 95340 KB Output is correct
18 Correct 113 ms 108396 KB Output is correct
19 Correct 59 ms 72684 KB Output is correct
20 Correct 60 ms 72684 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 86636 KB Output is correct
2 Correct 112 ms 98796 KB Output is correct
3 Correct 102 ms 99436 KB Output is correct
4 Correct 122 ms 119404 KB Output is correct
5 Correct 59 ms 72428 KB Output is correct
6 Correct 60 ms 72396 KB Output is correct
7 Correct 122 ms 117996 KB Output is correct
8 Correct 126 ms 114152 KB Output is correct
9 Correct 119 ms 113388 KB Output is correct
10 Correct 119 ms 116204 KB Output is correct
11 Correct 121 ms 115308 KB Output is correct
12 Correct 121 ms 113152 KB Output is correct
13 Correct 98 ms 103916 KB Output is correct
14 Correct 112 ms 118252 KB Output is correct
15 Correct 91 ms 98796 KB Output is correct
16 Correct 128 ms 120684 KB Output is correct
17 Correct 94 ms 95340 KB Output is correct
18 Correct 113 ms 108396 KB Output is correct
19 Correct 59 ms 72684 KB Output is correct
20 Correct 60 ms 72684 KB Output is correct
21 Correct 100 ms 95468 KB Output is correct
22 Correct 103 ms 98540 KB Output is correct
23 Correct 105 ms 105964 KB Output is correct
24 Correct 121 ms 118636 KB Output is correct
25 Correct 58 ms 72428 KB Output is correct
26 Correct 59 ms 72428 KB Output is correct
27 Correct 117 ms 113644 KB Output is correct
28 Correct 122 ms 116972 KB Output is correct
29 Correct 118 ms 112364 KB Output is correct
30 Correct 131 ms 115436 KB Output is correct
31 Correct 120 ms 112620 KB Output is correct
32 Correct 116 ms 111340 KB Output is correct
33 Correct 105 ms 107628 KB Output is correct
34 Correct 115 ms 116868 KB Output is correct
35 Correct 106 ms 108908 KB Output is correct
36 Correct 111 ms 117612 KB Output is correct
37 Correct 57 ms 72752 KB Output is correct
38 Correct 61 ms 72684 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 144 ms 146412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 153 ms 146412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 86636 KB Output is correct
2 Correct 112 ms 98796 KB Output is correct
3 Correct 102 ms 99436 KB Output is correct
4 Correct 122 ms 119404 KB Output is correct
5 Correct 59 ms 72428 KB Output is correct
6 Correct 60 ms 72396 KB Output is correct
7 Correct 122 ms 117996 KB Output is correct
8 Correct 126 ms 114152 KB Output is correct
9 Correct 119 ms 113388 KB Output is correct
10 Correct 119 ms 116204 KB Output is correct
11 Correct 121 ms 115308 KB Output is correct
12 Correct 121 ms 113152 KB Output is correct
13 Correct 98 ms 103916 KB Output is correct
14 Correct 112 ms 118252 KB Output is correct
15 Correct 91 ms 98796 KB Output is correct
16 Correct 128 ms 120684 KB Output is correct
17 Correct 94 ms 95340 KB Output is correct
18 Correct 113 ms 108396 KB Output is correct
19 Correct 59 ms 72684 KB Output is correct
20 Correct 60 ms 72684 KB Output is correct
21 Runtime error 144 ms 146412 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 138 ms 146496 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 86636 KB Output is correct
2 Correct 112 ms 98796 KB Output is correct
3 Correct 102 ms 99436 KB Output is correct
4 Correct 122 ms 119404 KB Output is correct
5 Correct 59 ms 72428 KB Output is correct
6 Correct 60 ms 72396 KB Output is correct
7 Correct 122 ms 117996 KB Output is correct
8 Correct 126 ms 114152 KB Output is correct
9 Correct 119 ms 113388 KB Output is correct
10 Correct 119 ms 116204 KB Output is correct
11 Correct 121 ms 115308 KB Output is correct
12 Correct 121 ms 113152 KB Output is correct
13 Correct 98 ms 103916 KB Output is correct
14 Correct 112 ms 118252 KB Output is correct
15 Correct 91 ms 98796 KB Output is correct
16 Correct 128 ms 120684 KB Output is correct
17 Correct 94 ms 95340 KB Output is correct
18 Correct 113 ms 108396 KB Output is correct
19 Correct 59 ms 72684 KB Output is correct
20 Correct 60 ms 72684 KB Output is correct
21 Correct 100 ms 95468 KB Output is correct
22 Correct 103 ms 98540 KB Output is correct
23 Correct 105 ms 105964 KB Output is correct
24 Correct 121 ms 118636 KB Output is correct
25 Correct 58 ms 72428 KB Output is correct
26 Correct 59 ms 72428 KB Output is correct
27 Correct 117 ms 113644 KB Output is correct
28 Correct 122 ms 116972 KB Output is correct
29 Correct 118 ms 112364 KB Output is correct
30 Correct 131 ms 115436 KB Output is correct
31 Correct 120 ms 112620 KB Output is correct
32 Correct 116 ms 111340 KB Output is correct
33 Correct 105 ms 107628 KB Output is correct
34 Correct 115 ms 116868 KB Output is correct
35 Correct 106 ms 108908 KB Output is correct
36 Correct 111 ms 117612 KB Output is correct
37 Correct 57 ms 72752 KB Output is correct
38 Correct 61 ms 72684 KB Output is correct
39 Runtime error 144 ms 146412 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 86636 KB Output is correct
2 Correct 112 ms 98796 KB Output is correct
3 Correct 102 ms 99436 KB Output is correct
4 Correct 122 ms 119404 KB Output is correct
5 Correct 59 ms 72428 KB Output is correct
6 Correct 60 ms 72396 KB Output is correct
7 Correct 122 ms 117996 KB Output is correct
8 Correct 126 ms 114152 KB Output is correct
9 Correct 119 ms 113388 KB Output is correct
10 Correct 119 ms 116204 KB Output is correct
11 Correct 121 ms 115308 KB Output is correct
12 Correct 121 ms 113152 KB Output is correct
13 Correct 98 ms 103916 KB Output is correct
14 Correct 112 ms 118252 KB Output is correct
15 Correct 91 ms 98796 KB Output is correct
16 Correct 128 ms 120684 KB Output is correct
17 Correct 94 ms 95340 KB Output is correct
18 Correct 113 ms 108396 KB Output is correct
19 Correct 59 ms 72684 KB Output is correct
20 Correct 60 ms 72684 KB Output is correct
21 Correct 100 ms 95468 KB Output is correct
22 Correct 103 ms 98540 KB Output is correct
23 Correct 105 ms 105964 KB Output is correct
24 Correct 121 ms 118636 KB Output is correct
25 Correct 58 ms 72428 KB Output is correct
26 Correct 59 ms 72428 KB Output is correct
27 Correct 117 ms 113644 KB Output is correct
28 Correct 122 ms 116972 KB Output is correct
29 Correct 118 ms 112364 KB Output is correct
30 Correct 131 ms 115436 KB Output is correct
31 Correct 120 ms 112620 KB Output is correct
32 Correct 116 ms 111340 KB Output is correct
33 Correct 105 ms 107628 KB Output is correct
34 Correct 115 ms 116868 KB Output is correct
35 Correct 106 ms 108908 KB Output is correct
36 Correct 111 ms 117612 KB Output is correct
37 Correct 57 ms 72752 KB Output is correct
38 Correct 61 ms 72684 KB Output is correct
39 Runtime error 144 ms 146412 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -