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