oj.uz

Submission #249366

# Submission time Handle Problem Language Result Execution time Memory
249366 2020-07-14T16:54:31 Z vanic OGLEDALA (COI15_ogledala) C++14
41 / 100
 4000 ms 270452 KB 
#include <iostream>
#include <algorithm>
#include <math.h>
#include <set>
#include <queue>

using namespace std;

const int maxn=3e5+5;
typedef long long ll;
const ll inf=1e18;

class Compare{
public:
	bool operator()(pair < ll, ll > a, pair < ll, ll > b){
		if(a.first!=b.first){
			return a.first<b.first;
		}
		return a.second>b.second;
	}
};

priority_queue < pair < ll, ll >, vector < pair < ll, ll > >, Compare > svi;
set < pair < ll, ll > > s;
ll a[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll m, n, q;
	cin >> m >> n >> q;
	s.insert({0, m-1});
	set < pair < ll, ll > >::const_iterator it;
	pair < ll, ll > p;
	for(int i=0; i<n; i++){
		cin >> a[i];
		a[i]--;
			it=s.upper_bound({a[i], inf});
			it--;
			p=*it;
			s.erase(it);
			if(p.first!=a[i]){
				s.insert({p.first, a[i]-1});
			}
			if(p.second!=a[i]){
				s.insert({a[i]+1, p.second});
			}
		
	}
	for(it=s.begin(); it!=s.end(); it++){
		p=*it;
		svi.push({p.second-p.first+1, p.first});
	}
	ll val;
	ll pos=n;
	ll b;
	ll br;
	for(int i=0; i<q; i++){
		cin >> b;
		if(b<=pos){
			cout << a[b-1]+1 << '\n';
			continue;
		}
		while(pos<b){
			p=svi.top();
			svi.pop();
			br=p.first;
//			cout << "radim " << p.first << " " << p.second << endl;
			val=p.second+(br-1)/2;
			if(val!=p.second){
				svi.push({val-p.second, p.second});
			}
			if(val!=p.second+br-1){
				svi.push({p.second+br-1-val, val+1});
			}
			pos++;
		}
		cout << val+1 << '\n';
	}
	return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 35 ms 2804 KB Output is correct
4 Correct 34 ms 2808 KB Output is correct
5 Correct 130 ms 8852 KB Output is correct
6 Correct 132 ms 10472 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8808 KB Output is correct
2 Correct 52 ms 8816 KB Output is correct
3 Correct 154 ms 16860 KB Output is correct
4 Correct 158 ms 16988 KB Output is correct
5 Correct 181 ms 17072 KB Output is correct
6 Correct 163 ms 17116 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4045 ms 270452 KB Time limit exceeded
2 Halted 0 ms 0 KB -