oj.uz

Submission #104942

# Submission time Handle Problem Language Result Execution time Memory
104942 2019-04-09T21:37:12 Z Shtef OGLEDALA (COI15_ogledala) C++14
19 / 100
 216 ms 15736 KB 
#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct nes{
	int l, r;
	friend bool operator <(nes x, nes y){
		if(x.r - x.l + 1 == y.r - y.l + 1)
			return x.l < y.l;
		return x.r - x.l + 1 > y.r - y.l + 1;
	}
};

int m, n, q, a[300005], c[300005];
multiset <nes> s;
set <int> b;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m >> n >> q;
for(int i = 1 ; i <= n ; ++i){
	cin >> a[i];
	c[i] = a[i];
}
if(a[1] != 1){
	s.insert((nes){1, a[1] - 1});
}
for(int i = 2 ; i <= n ; ++i){
	if(a[i] != a[i - 1] + 1){
		s.insert((nes){a[i - 1] + 1, a[i] - 1});
	}
}
if(a[n] != m){
	s.insert((nes){a[n] + 1, m});
}
for(int i = n + 1 ; i <= min(m, 300000) ; ++i){
	nes o = *s.begin();
	s.erase(s.begin());
	int mid = (o.l + o.r) / 2;
	c[i] = mid;
	if(mid > o.l){
		s.insert((nes){o.l, mid - 1});
	}
	if(o.r > mid){
		s.insert((nes){mid + 1, o.r});
	}
}
for(int i = 0 ; i < q ; ++i){
	int x;
	cin >> x;
	cout << c[x] << endl;
}

return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 143 ms 3804 KB Output is correct
4 Correct 142 ms 3848 KB Output is correct
5 Correct 216 ms 9180 KB Output is correct
6 Correct 208 ms 9720 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 15680 KB Output is correct
2 Correct 122 ms 15736 KB Output is correct
3 Incorrect 162 ms 15648 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 15696 KB Output isn't correct
2 Halted 0 ms 0 KB -