제출 #719461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
719461		qwerasdfzxcl	푸드 코트 (JOI21_foodcourt)	C++17	100 / 100	641 ms	70344 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Node{
	ll x, mn;
	int mni;
	Node(){}
	Node(ll _x, ll _mn, int _mni): x(_x), mn(_mn), mni(_mni) {}

	Node operator + (const Node &N) const{
		if (mni==-1) return N;
		if (N.mni==-1) return *this;

		Node ret;
		ret.x = x + N.x;
		if (mn < x+N.mn) ret.mn = mn, ret.mni = mni;
		else ret.mn = x + N.mn, ret.mni = N.mni;
		return ret;
	}
};

template<typename T>
struct Seg{
	T tree[1001000], I;
	int sz;

	void update(int i, int l, int r, int p, T x){
		if (r<p || p<l) return;
		if (l==r){
			tree[i] = x;
			return;
		}

		int m = (l+r)>>1;
		update(i<<1, l, m, p, x); update(i<<1|1, m+1, r, p, x);
		tree[i] = tree[i<<1] + tree[i<<1|1];
	}
	T query(int i, int l, int r, int s, int e) const{
		if (r<s || e<l) return I;
		if (s<=l && r<=e) return tree[i];

		int m = (l+r)>>1;
		return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
	}

	void init(int n, T _I){sz = n, I = _I; fill(tree, tree+(sz+1)*4, I);}
	void update(int p, T x){update(1, 0, sz, p, x);}
	T query(int l, int r) const{return query(1, 0, sz, l, r);}
};

int search(const Seg<ll> &S, int i, int l, int r, int e, ll x){
	if (l==r) return l;

	int m = (l+r)>>1;
	if (e <= m || S.tree[i<<1] >= x) return search(S, i<<1, l, m, e, x);
	return search(S, i<<1|1, m+1, r, e, x-S.tree[i<<1]);
}

int find(const Seg<ll> &S, int r, ll x){
	x = S.query(0, r) - x;
	return search(S, 1, 0, S.sz, r, x);
}

Seg<Node> tree1;
Seg<ll> tree2;

vector<pair<int, ll>> on[250250], off[250250], Q[250250];
int col[250250], ans[250250];

int main(){
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);

	for (int i=1;i<=q;i++){
		int op;
		scanf("%d", &op);
		if (op==1){
			int l, r, c, k;
			scanf("%d %d %d %d", &l, &r, &c, &k);
			on[l].emplace_back(i, k);
			off[r+1].emplace_back(i, k);
			col[i] = c;
		}
		else if (op==2){
			int l, r, k;
			scanf("%d %d %d", &l, &r, &k);
			on[l].emplace_back(i, -k);
			off[r+1].emplace_back(i, -k);
		}
		else{
			int x;
			ll y;
			scanf("%d %lld", &x, &y);
			Q[x].emplace_back(i, y);
		}
	}

	tree1.init(q, Node(0, 0, -1));
	tree2.init(q, 0);
	tree1.update(0, Node(0, 0, 0));

	for (int i=1;i<=n;i++){
		for (auto &[j, x]:on[i]){
			tree1.update(j, Node(x, x, j));
			if (x>0) tree2.update(j, x);
		} 
		for (auto &[j, x]:off[i]){
			tree1.update(j, Node(0, 0, -1));
			if (x>0) tree2.update(j, 0);
		} 

		// printf("%d: ", i);
		// for (int j=1;j<=q;j++) printf("%lld ", tree2.query(j, j));
		// printf("\n");

		for (auto &[j, x]:Q[i]){
			auto [S, mn, mni] = tree1.query(0, j);
			ll cnt = tree1.query(mni+1, j).x;

			// printf("%d %lld -> %lld %lld %d %lld -> %d\n", j, x, S, mn, mni, cnt, find(tree2, j, cnt-x));
			if (cnt < x) ans[j] = -1;
			else ans[j] = col[find(tree2, j, cnt-x)];
		}
	}

	for (int i=1;i<=q;i++) if (ans[i]){
		printf("%d\n", ans[i]==-1?0:ans[i]);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d", &op);
      |   ~~~~~^~~~~~~~~~~
foodcourt.cpp:81:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |    scanf("%d %d %d %d", &l, &r, &c, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:88:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |    scanf("%d %d %d", &l, &r, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:95:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |    scanf("%d %lld", &x, &y);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11