oj.uz

답안 #425943

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
425943 2021-06-13T12:29:23 Z Kevin_Zhang_TW 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 577 ms 48092 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;
const ll inf = 1ll << 60;

#define int ll

int n, m, q;
int res[MAX_N], cid[MAX_N];

bool is_leave[MAX_N];

//          position, delta
vector<pair<int,int>> rec[MAX_N];
//         time, k
vector<pair<int,ll>> allq[MAX_N];

struct sgt {
	struct node {
		ll mn, pos, tg;
		void operator += (ll v) {
			mn += v, tg += v;
		}
		node (node a, node b) {
			mn = min(a.mn, b.mn);
			if (a.mn == mn) pos = a.pos;
			else pos = b.pos;
			tg = 0;
		}
		node () : mn(0), pos(0), tg(0) {}
		pair<ll,ll> get() { return make_pair(mn, pos); }
	};
	int n;
	vector<node> val;
	sgt(int n) : n(n) {
		val.resize(n<<1);
		for (int i = 0;i < n;++i)
			val[i+n].pos = i;
	}
	void add(int l, int r, ll v) {
		int sl = l+=n, sr = r+=n;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) val[l++] += v;
			if (r&1) val[--r] += v;
		}
		for (;sl>>=1, sr>>=1;) 
			upd(sl), upd(sr);
	}
	void upd(int i) {
		if (i >= n) return;
		ll &t = val[i].tg;
		val[i<<1] += t, val[i<<1|1] += t;
		val[i] = node(val[i<<1], val[i<<1|1]);
	}
	pair<ll,ll> qmn(int l, int r) {
		l += n, r += n;
		for (int i = 19;i > 0;--i) upd(l>>i), upd(r>>i);
		pair<ll,ll> res {inf, n};
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) chmin(res, val[l++].get());
			if (r&1) chmin(res, val[--r].get());
		}
		return res;
	} 
};

// t1 for +
// t2 for -
struct bit { 
	int n;
	vector<ll> val;
	bit (int n) : n(n) {
		val.resize(n);
	}
	void add(int i, ll v) {
		for (;i < n;i += i&-i)
			val[i] += v;
	}
	ll qry(int i) {
		ll res = 0;
		for (;i;i^=i&-i) res += val[i];
		return res;
	}
	ll qry(int l, int r) { return qry(r) - qry(l-1); }
	int kth(ll k) {
		int res = 0;
		for (int i = 1<<19;i > 0;i>>=1) {
			if ((i|res) >= n || k <= val[res|i]) continue;
			assert(k > val[res|i]);
			k -= val[res|=i];
		}
		return res + 1; 
	} 
};

void solve() {

	bit t1(q + 10), t2(q + 10);
	sgt tree(q);

	for (int i = 1;i <= n;++i) {
		for (auto [j, d] : rec[i]) {
			tree.add(j, q, d);
			if (is_leave[j]) 
				t2.add(j, -d);
			else 
				t1.add(j, d);
		}

		for (auto [t, k] : allq[i]) {
			auto [v, p] = tree.qmn(0, t); 


			ll rk = t1.qry(p) + k + t2.qry(p+1, t);
			
			int ind = t1.kth(rk);
			//DE(t, k, v, p, rk, ind, cid[ind]);
			if (t == 3) {
				for (int j = 1;j <= 2;++j)
					DE(j, t1.qry(j));
			}

			//DE(t1.qry(ind), rk, t1.qry(ind+1));
			
			res[t] = ind >= t ? 0 : cid[ind]; 
		}
	} 
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> q; ++q;
	fill(res, res + q, -1);

	for (int t, l, r, k, i = 1;i < q;++i) {
		cin >> t;
		if (t == 1) {
			cin >> l >> r >> cid[i] >> k;
			rec[l].pb(i, k);
			rec[r+1].pb(i,-k);
		}
		if (t == 2) {
			cin >> l >> r >> k;
			is_leave[i] = true;
			rec[l].pb(i, -k);
			rec[r+1].pb(i, k);
		}
		if (t == 3) {
			cin >> l >> k;
			allq[l].pb(i, k);
		}
	}

	solve();

	for (int i = 0;i < q;++i) {
		if (res[i] == -1) continue;
		cout << res[i] << '\n';
	}

}

Compilation message

foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
foodcourt.cpp:135:6: note: in expansion of macro 'DE'
  135 |      DE(j, t1.qry(j));
      |      ^~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 22756 KB Output is correct
2 Correct 142 ms 23636 KB Output is correct
3 Correct 126 ms 23800 KB Output is correct
4 Correct 100 ms 20988 KB Output is correct
5 Correct 119 ms 22516 KB Output is correct
6 Correct 137 ms 23784 KB Output is correct
7 Correct 59 ms 21584 KB Output is correct
8 Correct 54 ms 21044 KB Output is correct
9 Correct 82 ms 22996 KB Output is correct
10 Correct 94 ms 20864 KB Output is correct
11 Correct 108 ms 23364 KB Output is correct
12 Correct 106 ms 23428 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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