oj.uz

Submission #243486

# Submission time Handle Problem Language Result Execution time Memory
243486 2020-07-01T08:59:41 Z vanic Segway (COI19_segway) C++14
40 / 100
 1000 ms 1172 KB 
#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];
bitset < maxp > boost;
int sol[maxn];
vector < int > ind;
logaritamska L;

int main(){
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d%d%d", &v[i][0], &v[i][1], &v[i][2]);
		q.push({v[i][0], i});
	}
	int m;
	scanf("%d", &m);
	int a;
	for(int i=0; i<m; i++){
		scanf("%d", &a);
		boost[a]=1;
	}
	L.update(maxp, n);
	pair < int, int > p;
	while(!q.empty()){
		p=q.top();
		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){
				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++){
		printf("%d\n", sol[i]);
	}
	return 0;
}

Compilation message

segway.cpp: In function 'int main()':
segway.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
segway.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &v[i][0], &v[i][1], &v[i][2]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
segway.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
segway.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 12 ms 384 KB Output is correct
3 Correct 39 ms 384 KB Output is correct
4 Correct 149 ms 632 KB Output is correct
5 Execution timed out 1078 ms 1172 KB Time limit exceeded

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 12 ms 384 KB Output is correct
9 Correct 13 ms 384 KB Output is correct
10 Correct 17 ms 384 KB Output is correct
11 Correct 13 ms 384 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 12 ms 384 KB Output is correct
3 Correct 39 ms 384 KB Output is correct
4 Correct 149 ms 632 KB Output is correct
5 Execution timed out 1078 ms 1172 KB Time limit exceeded