oj.uz

답안 #437203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437203 2021-06-26T03:49:42 Z maomao90 푸드 코트 (JOI21_foodcourt) C++17
7 / 100
 623 ms 42280 KB 
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 300005

struct event {
	int v, i, t;
};
struct query {
	ll v;
   	int i;
};

int n, m, q;
vector<event> events[MAXN];
vector<query> queries[MAXN];
int grp[MAXN], ans[MAXN];

namespace st {
#define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
	ll mn[MAXN * 4], lazy[MAXN * 4];
	void propo(int u, int lo, int hi) {
		if (lazy[u] == 0 || lo == hi) return;
		MLR;
		lazy[lc] += lazy[u];
		lazy[rc] += lazy[u];
		mn[lc] += lazy[u];
		mn[rc] += lazy[u];
		lazy[u] = 0;
	}
	void incre(int s, int e, int x, int u = 1, int lo = 1, int hi = q) {
		if (lo >= s && hi <= e) {
			lazy[u] += x;
			mn[u] += x;
			return;
		}
		propo(u, lo, hi);
		MLR;
		if (s <= mid) {
			incre(s, e, x, lc, lo, mid);
		}
		if (e > mid) {
			incre(s, e, x, rc, mid + 1, hi);
		}
		mn[u] = min(mn[lc], mn[rc]);
	}
	ll qmn(int s, int e, int u = 1, int lo = 1, int hi = q) {
		if (lo >= s && hi <= e) {
			return mn[u];
		}
		propo(u, lo, hi);
		MLR;
		if (e <= mid) {
			return qmn(s, e, lc, lo, mid);
		} else if (s > mid) {
			return qmn(s, e, rc, mid + 1, hi);
		} else {
			return min(qmn(s, e, lc, lo, mid), qmn(s, e, rc, mid + 1, hi));
		}
	}
}

namespace fw {
	ll v[MAXN];
	void incre(int i, int x) {
		for (; i <= q; i += i & -i) v[i] += x;
	}
	ll qsm(int i) {
		ll res = 0;
		for (; i > 0; i -= i & -i) res += v[i];
		return res;
	}
	int get(ll x) {
		int id = 0;
		RREP (k, 25, 0) {
			id ^= (1 << k);
			if (id > q || v[id] >= x) {
				id ^= (1 << k);
			} else {
				x -= v[id];
			}
		}
		id++;
		return id;
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	memset(ans, -1, sizeof ans);
	REP (i, 1, q + 1) {
		int t; scanf("%d", &t);
		if (t == 1) {
			int l, r, c, k; scanf("%d%d%d%d", &l, &r, &c, &k);
			events[l].pb({k, i, 0});
			events[r + 1].pb({-k, i, 0});
			grp[i] = c;
		} else if (t == 2) {
			int l, r, k; scanf("%d%d%d", &l, &r, &k);
			events[l].pb({-k, i, 1});
			events[r + 1].pb({k, i, 1});
		} else {
			int a; ll b; scanf("%d%lld", &a, &b);
			queries[a].pb({b, i});
		}
	}
	REP (i, 1, n + 1) {
		for (event &e : events[i]) {
			auto [v, i, t] = e;
			st::incre(i, q, v);
			if (!t) {
				fw::incre(i, v);
			}
		}
		for (query q : queries[i]) {
			auto [v, i] = q;
			ll rem = st::qmn(i, i) - st::qmn(1, i);
			ll tot = fw::qsm(i);
			ll rmv = tot - rem;
			v += rmv;
			if (v > tot) {
				ans[i] = 0;
			} else {
				int id = fw::get(v);
				ans[i] = grp[id];
			}
		}
	}
	REP (i, 1, q + 1) {
		if (ans[i] == -1) continue;
		printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message

foodcourt.cpp: In function 'void st::propo(int, int, int)':
foodcourt.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
foodcourt.cpp:60:3: note: in expansion of macro 'MLR'
   60 |   MLR;
      |   ^~~
foodcourt.cpp:56:17: warning: unused variable 'mid' [-Wunused-variable]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                 ^~~
foodcourt.cpp:60:3: note: in expansion of macro 'MLR'
   60 |   MLR;
      |   ^~~
foodcourt.cpp: In function 'void st::incre(int, int, int, int, int, int)':
foodcourt.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
foodcourt.cpp:74:3: note: in expansion of macro 'MLR'
   74 |   MLR;
      |   ^~~
foodcourt.cpp: In function 'll st::qmn(int, int, int, int, int)':
foodcourt.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
foodcourt.cpp:88:3: note: in expansion of macro 'MLR'
   88 |   MLR;
      |   ^~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:128:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |   int t; scanf("%d", &t);
      |          ~~~~~^~~~~~~~~~
foodcourt.cpp:130:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |    int l, r, c, k; scanf("%d%d%d%d", &l, &r, &c, &k);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:135:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |    int l, r, k; scanf("%d%d%d", &l, &r, &k);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:139:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |    int a; ll b; scanf("%d%lld", &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 22044 KB Output is correct
2 Correct 127 ms 22136 KB Output is correct
3 Correct 121 ms 22096 KB Output is correct
4 Correct 113 ms 22080 KB Output is correct
5 Correct 122 ms 22100 KB Output is correct
6 Correct 116 ms 22084 KB Output is correct
7 Correct 54 ms 20528 KB Output is correct
8 Correct 59 ms 20516 KB Output is correct
9 Correct 109 ms 21976 KB Output is correct
10 Correct 115 ms 22216 KB Output is correct
11 Correct 107 ms 22096 KB Output is correct
12 Correct 110 ms 22088 KB Output is correct
13 Correct 98 ms 21460 KB Output is correct
14 Correct 96 ms 21948 KB Output is correct
15 Correct 105 ms 22212 KB Output is correct
16 Correct 108 ms 22200 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 623 ms 40700 KB Output is correct
2 Correct 424 ms 37364 KB Output is correct
3 Correct 615 ms 42280 KB Output is correct
4 Correct 429 ms 37832 KB Output is correct
5 Incorrect 451 ms 37700 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 22040 KB Output is correct
2 Correct 136 ms 22340 KB Output is correct
3 Incorrect 122 ms 22536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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