This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
const int maxn=2e4+5, maxp=305;
struct logaritamska{
int l[maxp+5];
void update(int x, int val){
for(; x<=maxp; x+=(x & -x)){
l[x]+=val;
}
}
int query(int x){
int sol=0;
for(; x>0; x-=(x & -x)){
sol+=l[x];
}
return sol;
}
};
int v[maxn][3];
priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > q;
int loc[maxn];
int sad[maxp];
int acel[maxn];
bool boost[maxp];
int sol[maxn];
vector < int > ind;
logaritamska L;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i=0; i<n; i++){
cin >> v[i][0] >> v[i][1] >> v[i][2];
q.push({v[i][0], i});
}
int m;
cin >> m;
int a;
for(int i=0; i<m; i++){
cin >> a;
boost[a]=1;
}
L.update(maxp, n);
pair < int, int > p;
while(!q.empty()){
p=q.top();
// cout << "vrtim" << endl;
while(!q.empty() && p.first==q.top().first){
p=q.top();
q.pop();
ind.push_back(p.second);
L.update(maxp-loc[p.second], -1);
loc[p.second]++;
sad[loc[p.second]]++;
L.update(maxp-loc[p.second], 1);
if(loc[p.second]==300){
// cout << "kraj" << endl;
sol[p.second]=p.first;
continue;
}
if(!acel[p.second] && boost[loc[p.second]]){
acel[p.second]=(L.query(maxp-loc[p.second])-sad[loc[p.second]])%20;
}
if(acel[p.second]){
acel[p.second]--;
q.push({p.first+1, p.second});
}
else{
q.push({p.first+v[p.second][loc[p.second]/100], p.second});
}
}
while(!ind.empty()){
sad[loc[ind.back()]]--;
ind.pop_back();
}
}
for(int i=0; i<n; i++){
cout << sol[i] << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |