oj.uz

답안 #441394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441394 2021-07-05T06:40:50 Z cheetose 푸드 코트 (JOI21_foodcourt) C++17
21 / 100
 730 ms 36308 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a))
#define MEM_1(a) memset((a),-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define COMPRESS(a) sort(ALL(a));a.resize(unique(ALL(a))-a.begin())
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<ld> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const int MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };
int ddx[] = { -1,-2,1,-2,2,-1,2,1 }, ddy[] = { -2,-1,-2,1,-1,2,1,2 };

Pll lazy[524288];
ll tree[524288];
void g(Pll &p1,Pll p2){
	if(p1.Y<=p2.X){
		p1.X+=p2.X-p1.Y;
		p1.Y=p2.Y;
	}else{
		p1.Y+=p2.Y-p2.X;
	}
}
void propagation(int node,int S,int E){
	tree[node]=max(tree[node]-lazy[node].X,0ll)+lazy[node].Y;
	if(S!=E){
		int L=node<<1,R=L|1;
		g(lazy[L],lazy[node]);
		g(lazy[R],lazy[node]);
	}
	lazy[node]=mp(0,0);
}
void upd(int node,int S,int E,int i,int j,ll k){
	propagation(node,S,E);
	if (i>E || j<S)return;
	if(i<=S && E<=j){
		if(k>0)lazy[node].Y+=k;
		else lazy[node].X-=k;
		propagation(node,S,E);
		return;
	}
	upd(node<<1,S,(S+E)/2,i,j,k);
	upd(node<<1|1,(S+E)/2+1,E,i,j,k);
}
ll find(int node,int S,int E,int i,int j){
	propagation(node,S,E);
	if (i>E || j<S)return 0;
	if(i<=S && E<=j)return tree[node];
	return find(node<<1,S,(S+E)/2,i,j)+find(node<<1|1,(S+E)/2+1,E,i,j);
}

int t[250000],a[250000],b[250000],c[250000],ans[250000];
ll d[250000],cnt[250000];
ll tree2[524288];
void upd(int node, int S, int E, int k, ll dif){
	tree2[node] += dif;
	if (S == E)return;
	if (k <= (S + E) / 2)upd(node * 2, S, (S + E) / 2, k, dif);
	else upd(node * 2 + 1, (S + E) / 2 + 1, E, k, dif);
}
int findK(int node, int S, int E, ll k){
	if (S == E)return c[S];
	if (k <= tree2[node * 2])return findK(node * 2, S, (S + E) / 2, k);
	return findK(node * 2 + 1, (S + E) / 2 + 1, E, k - tree2[node * 2]);
}
int main(){
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	Viii E;
	fup(i,0,q-1,1){
		scanf("%d",t+i);
		if(t[i]==1){
			scanf("%d%d%d%lld",a+i,b+i,c+i,d+i);
			upd(1,1,n,a[i],b[i],d[i]);
			E.pb(iii(a[i],0,i));
			E.pb(iii(b[i]+1,1,i));
		}else if(t[i]==2){
			scanf("%d%d%lld",a+i,b+i,d+i);
			upd(1,1,n,a[i],b[i],-d[i]);
		}else{
			scanf("%d%lld",a+i,d+i);
			cnt[i]=find(1,1,n,a[i],a[i]);
			E.pb(iii(a[i],2,i));
		}
	}
	sort(ALL(E));
	for(auto [x,k,i]:E){
		if(k==0){
			upd(1,0,q-1,i,d[i]);
		}else if(k==1){
			upd(1,0,q-1,i,-d[i]);
		}else{
			ll tot=tree2[1];
			if(d[i]>cnt[i])ans[i]=0;
			else{
				ll K=tot-cnt[i]+d[i];
				ans[i]=findK(1,0,q-1,K);
			}
		}
	}
	fup(i,0,q-1,1){
		if(t[i]==3)printf("%d\n",ans[i]);
	}
}

Compilation message

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
foodcourt.cpp:99:2: note: in expansion of macro 'fup'
   99 |  fup(i,0,q-1,1){
      |  ^~~
foodcourt.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
foodcourt.cpp:130:2: note: in expansion of macro 'fup'
  130 |  fup(i,0,q-1,1){
      |  ^~~
foodcourt.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d%d%d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
foodcourt.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |   scanf("%d",t+i);
      |   ~~~~~^~~~~~~~~~
foodcourt.cpp:102:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |    scanf("%d%d%d%lld",a+i,b+i,c+i,d+i);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |    scanf("%d%d%lld",a+i,b+i,d+i);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:110:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |    scanf("%d%lld",a+i,d+i);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 102 ms 7564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 583 ms 27736 KB Output is correct
2 Correct 416 ms 25476 KB Output is correct
3 Correct 654 ms 28620 KB Output is correct
4 Correct 466 ms 30340 KB Output is correct
5 Correct 478 ms 30676 KB Output is correct
6 Correct 680 ms 35520 KB Output is correct
7 Correct 174 ms 20532 KB Output is correct
8 Correct 176 ms 20400 KB Output is correct
9 Correct 659 ms 36156 KB Output is correct
10 Correct 656 ms 36308 KB Output is correct
11 Correct 573 ms 32216 KB Output is correct
12 Correct 604 ms 34696 KB Output is correct
13 Correct 630 ms 32472 KB Output is correct
14 Correct 659 ms 34740 KB Output is correct
15 Correct 629 ms 34636 KB Output is correct
16 Correct 616 ms 34684 KB Output is correct
17 Correct 730 ms 34616 KB Output is correct
18 Correct 727 ms 33552 KB Output is correct
19 Correct 700 ms 34744 KB Output is correct
20 Correct 634 ms 33684 KB Output is correct
21 Correct 603 ms 34684 KB Output is correct
22 Correct 672 ms 34656 KB Output is correct
23 Correct 636 ms 34684 KB Output is correct
24 Correct 622 ms 34608 KB Output is correct
25 Correct 471 ms 34116 KB Output is correct
26 Correct 487 ms 34464 KB Output is correct
27 Correct 479 ms 34408 KB Output is correct

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 119 ms 7776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -