Submission #12901167


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int D, L, N, F[101010]; ll T[101010];
vector<int> days[101010];
vector<int> humans[101010];
ll ans[101010];
//---------------------------------------------------------------------------------------------------
pair<ll, int> dp[31][101010];
void solve(int dish) {
	int n = days[dish].size();

	if (n == 0) return;

	rep(i, 0, n) {
		int j = (i + 1) % n;
		int d = days[dish][j] - days[dish][i];
		if (d <= 0) d += D;

		int cnt = 1 + (d - 1) / L;
		dp[0][i] = { cnt, j };
	}
	rep(p, 1, 31) rep(i, 0, n) {
		auto pa = dp[p - 1][i];
		auto pa2 = dp[p - 1][pa.second];
		dp[p][i] = { pa.first + pa2.first, pa2.second };
	}

	fore(h, humans[dish]) {
		int x = F[h] % D;
		auto ite = lower_bound(all(days[dish]), x);

		if (ite != days[dish].end() && *ite == x) ans[h]++;
		T[h]--;

		ite = upper_bound(all(days[dish]), x);

		int d = 0, cu = 0;
		if (ite == days[dish].end()) d = D - x + days[dish][0];
		else d = *ite - x, cu = ite - days[dish].begin();

		T[h] -= (d - 1) / L;
		if (T[h] <= 0) continue;
		T[h]--;
		ans[h]++;

		rrep(p, 30, 0) {
			auto pa = dp[p][cu];
			if (pa.first <= T[h]) {
				ans[h] += 1 << p;
				T[h] -= pa.first;
				cu = pa.second;
			}
		}
	}
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> D >> L >> N;
	rep(i, 0, D) {
		int C; cin >> C;
		days[C].push_back(i);
	}
	rep(i, 0, N) {
		int K; cin >> K >> F[i] >> T[i];
		F[i]--;
		humans[K].push_back(i);
	}

	rep(dish, 1, 101010) solve(dish);
	rep(i, 0, N) printf("%d\n", ans[i]);
}





Submission Info

Submission Time
Task M - Cafeteria
User hamayanhamayan
Language C++ (GCC 9.2.1)
Score 6
Code Size 2894 Byte
Status AC
Exec Time 145 ms
Memory 28228 KB

Compile Error

./Main.cpp: In function ‘void _main()’:
./Main.cpp:102:24: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘ll’ {aka ‘long long int’} [-Wformat=]
  102 |  rep(i, 0, N) printf("%d\n", ans[i]);
      |                       ~^     ~~~~~~
      |                        |          |
      |                        int        ll {aka long long int}
      |                       %lld

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 6 / 6
Status
AC × 3
AC × 31
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 16 ms 8568 KB
02.txt AC 10 ms 8396 KB
03.txt AC 8 ms 8432 KB
04.txt AC 11 ms 8568 KB
05.txt AC 9 ms 8572 KB
06.txt AC 10 ms 8520 KB
07.txt AC 11 ms 8620 KB
08.txt AC 8 ms 8664 KB
09.txt AC 11 ms 8608 KB
10.txt AC 10 ms 8452 KB
11.txt AC 7 ms 8536 KB
12.txt AC 27 ms 10004 KB
13.txt AC 28 ms 9512 KB
14.txt AC 35 ms 10200 KB
15.txt AC 39 ms 11140 KB
16.txt AC 24 ms 9472 KB
17.txt AC 28 ms 9840 KB
18.txt AC 54 ms 11660 KB
19.txt AC 66 ms 12208 KB
20.txt AC 32 ms 9780 KB
21.txt AC 20 ms 9548 KB
22.txt AC 100 ms 14300 KB
23.txt AC 69 ms 11564 KB
24.txt AC 72 ms 11532 KB
25.txt AC 97 ms 13644 KB
26.txt AC 145 ms 28228 KB
27.txt AC 26 ms 9484 KB
28.txt AC 118 ms 22900 KB
s1.txt AC 8 ms 8548 KB
s2.txt AC 10 ms 8468 KB
s3.txt AC 11 ms 8580 KB