oj.uz

답안 #437204

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

#define int ll

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;
	}
}

main() {
	scanf("%lld%lld%lld", &n, &m, &q);
	memset(ans, -1, sizeof ans);
	REP (i, 1, q + 1) {
		int t; scanf("%lld", &t);
		if (t == 1) {
			int l, r, c, k; scanf("%lld%lld%lld%lld", &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("%lld%lld%lld", &l, &r, &k);
			events[l].pb({-k, i, 1});
			events[r + 1].pb({k, i, 1});
		} else {
			int a; ll b; scanf("%lld%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("%lld\n", ans[i]);
	}
	return 0;
}

Compilation message

foodcourt.cpp: In function 'void st::propo(ll, ll, ll)':
foodcourt.cpp:58:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
foodcourt.cpp:62:3: note: in expansion of macro 'MLR'
   62 |   MLR;
      |   ^~~
foodcourt.cpp:58:17: warning: unused variable 'mid' [-Wunused-variable]
   58 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                 ^~~
foodcourt.cpp:62:3: note: in expansion of macro 'MLR'
   62 |   MLR;
      |   ^~~
foodcourt.cpp: In function 'void st::incre(ll, ll, ll, ll, ll, ll)':
foodcourt.cpp:58:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
foodcourt.cpp:76:3: note: in expansion of macro 'MLR'
   76 |   MLR;
      |   ^~~
foodcourt.cpp: In function 'll st::qmn(ll, ll, ll, ll, ll)':
foodcourt.cpp:58:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
foodcourt.cpp:90:3: note: in expansion of macro 'MLR'
   90 |   MLR;
      |   ^~~
foodcourt.cpp: At global scope:
foodcourt.cpp:126:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  126 | main() {
      | ^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  scanf("%lld%lld%lld", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:130:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   int t; scanf("%lld", &t);
      |          ~~~~~^~~~~~~~~~~~
foodcourt.cpp:132:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |    int l, r, c, k; scanf("%lld%lld%lld%lld", &l, &r, &c, &k);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:137:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |    int l, r, k; scanf("%lld%lld%lld", &l, &r, &k);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:141:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |    int a; ll b; scanf("%lld%lld", &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 23252 KB Output is correct
2 Correct 135 ms 23476 KB Output is correct
3 Correct 108 ms 23236 KB Output is correct
4 Correct 105 ms 23240 KB Output is correct
5 Correct 135 ms 23488 KB Output is correct
6 Correct 113 ms 23504 KB Output is correct
7 Correct 56 ms 22424 KB Output is correct
8 Correct 60 ms 22536 KB Output is correct
9 Correct 106 ms 23108 KB Output is correct
10 Correct 118 ms 23460 KB Output is correct
11 Correct 115 ms 23284 KB Output is correct
12 Correct 104 ms 23492 KB Output is correct
13 Correct 97 ms 22792 KB Output is correct
14 Correct 115 ms 23340 KB Output is correct
15 Correct 142 ms 23744 KB Output is correct
16 Correct 131 ms 23748 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 550 ms 40836 KB Output is correct
2 Correct 432 ms 37552 KB Output is correct
3 Correct 641 ms 42260 KB Output is correct
4 Correct 427 ms 37948 KB Output is correct
5 Incorrect 543 ms 38348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 22468 KB Output is correct
2 Correct 120 ms 22912 KB Output is correct
3 Incorrect 112 ms 22964 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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