Submission #126088

#TimeUsernameProblemLanguageResultExecution timeMemory
126088briansuLottery (CEOI18_lot)C++14
35 / 100
2307 ms988 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> ii; #define REP(i, n) for(int i = 0;i < n;i ++) #define REP1(i, n) for(int i = 1;i <= n;i ++) #define FILL(i, n) memset(i, n, sizeof(i)) #define X first #define Y second #define pb push_back #define SZ(_a) ((int)(_a).size()) #define ALL(_a) (_a).begin(), (_a).end() #ifdef brian #define IOS() template<typename T>void _do(T &&x){cerr<<x<<endl;} template<typename T, typename ...t> void _do(T &&x, t &&...X){cerr<<x<<", ";_do(X...);} #define debug(...) {\ fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\ _do(__VA_ARGS__);\ } #else #define IOS() ios_base::sync_with_stdio(0);cin.tie(0); #define debug(...) #define endl '\n' #endif const ll MAXn = 1e4 + 5; const ll INF = ll(1e17); const ll MOD = 1000000007; const ll bs = 880301; int dt[MAXn]; int qr[MAXn]; int d[MAXn], a[105][MAXn]; vector<ll> qdt; int main(){ IOS(); ll n, l; cin>>n>>l; REP1(i, n)cin>>d[i]; ll q; cin>>q; REP1(i, q)cin>>qr[i], qdt.pb(i); sort(ALL(qdt), [](int a,int b){return qr[a] < qr[b];}); REP1(dif, n - l) { REP1(j, n - dif)dt[j] = (d[j] != d[j + dif]) + dt[j-1]; vector<ll> v; REP1(i, n - l + 1 - dif)v.pb(i); sort(ALL(v), [&](int a,int b){return dt[a + l - 1] - dt[a - 1] < dt[b + l - 1] - dt[b - 1];}); ll it = 0; for(auto t:qdt)while(it < SZ(v) && qr[t] >= dt[v[it] + l - 1] - dt[v[it] - 1])a[t][v[it]]++, a[t][v[it] + dif]++, it++; } REP1(x, q - 1)REP1(i, n - l + 1)a[qdt[x]][i] += a[qdt[x]-1][i]; REP1(t, q)REP1(i, n - l + 1)cout<<a[t][i]<<" \n"[i == n - l + 1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...