oj.uz

Submission #422063

# Submission time Handle Problem Language Result Execution time Memory
422063 2021-06-09T16:52:30 Z errorgorn Food Court (JOI21_foodcourt) C++17
21 / 100
 647 ms 55364 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll INF=1e18;

struct node{
	int s,e,m;
	ll val=0,lazy=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy){
			val+=lazy;
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			lazy=0;
		}
	}
	
	void update(int i,int j,ll k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			val=min(l->val,r->val);
		}
	}
	
	ll query(int i,int j){
		propo();
		
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return min(l->query(i,m),r->query(m+1,j));
	}
} *root=new node(0,250005);

struct upd{
	ll pos;
	ll t;
	ll num;
};

int n,m,q;
vector<upd> u;
vector<ii> qu[250005]; //(length,time)

ll ans[250005];

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	memset(ans,-1,sizeof(ans));
	
	cin>>n>>m>>q;
	
	ll a,b,c,d;
	rep(x,1,q+1){
		cin>>a;
		
		if (a==1){
			cin>>a>>b>>c>>d;
			
			u.pub(upd({a,x,d}));
			u.pub(upd({b+1,x,-d}));
		}
		else if (a==2){
			cin>>a>>b>>c;
		
			u.pub(upd({a,x,-c}));
			u.pub(upd({b+1,x,c}));
		}
		else{
			cin>>a>>b;
			qu[a].pub(ii(b,x));
		}
	}
	
	sort(all(u),[](upd i,upd j){
		return i.pos>j.pos;
	});
	
	rep(x,1,n+1){
		while (!u.empty() && u.back().pos==x){
			//cout<<"update: "<<u.back().t<<" "<<u.back().num<<endl;
			root->update(u.back().t,250005,u.back().num);
			u.pob();
		}
		
		for (auto &it:qu[x]){
			ll num=root->query(it.se,it.se)-root->query(0,it.se);
			
			//cout<<it.se<<" "<<num<<endl;
			
			if (num<it.fi) ans[it.se]=0;
			else ans[it.se]=1;
		}
	}
	
	rep(x,1,q+1) if (ans[x]!=-1) cout<<ans[x]<<endl;
}

Compilation message

foodcourt.cpp: In constructor 'node::node(int, int)':
foodcourt.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 39500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 39500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 42952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 53684 KB Output is correct
2 Correct 440 ms 47032 KB Output is correct
3 Correct 618 ms 53748 KB Output is correct
4 Correct 426 ms 53072 KB Output is correct
5 Correct 452 ms 52968 KB Output is correct
6 Correct 613 ms 54332 KB Output is correct
7 Correct 220 ms 55092 KB Output is correct
8 Correct 255 ms 54720 KB Output is correct
9 Correct 579 ms 51624 KB Output is correct
10 Correct 560 ms 51644 KB Output is correct
11 Correct 623 ms 54420 KB Output is correct
12 Correct 615 ms 54492 KB Output is correct
13 Correct 641 ms 54584 KB Output is correct
14 Correct 647 ms 54720 KB Output is correct
15 Correct 615 ms 54588 KB Output is correct
16 Correct 612 ms 54580 KB Output is correct
17 Correct 610 ms 54720 KB Output is correct
18 Correct 615 ms 54536 KB Output is correct
19 Correct 620 ms 54372 KB Output is correct
20 Correct 606 ms 54584 KB Output is correct
21 Correct 636 ms 54584 KB Output is correct
22 Correct 631 ms 54460 KB Output is correct
23 Correct 637 ms 54412 KB Output is correct
24 Correct 618 ms 54456 KB Output is correct
25 Correct 601 ms 55364 KB Output is correct
26 Correct 583 ms 55240 KB Output is correct
27 Correct 419 ms 53408 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 39500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 41612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 39500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 39500 KB Output isn't correct
2 Halted 0 ms 0 KB -