oj.uz

Submission #104944

# Submission time Handle Problem Language Result Execution time Memory
104944 2019-04-09T21:38:18 Z Shtef OGLEDALA (COI15_ogledala) C++14
41 / 100
 348 ms 45584 KB 
#include <iostream>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;

struct nes{
	ll 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;
	}
};

ll m, n, q, a[300005], c[300005];
multiset <nes> s;
set <ll> 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, 300000LL) ; ++i){
	nes o = *s.begin();
	s.erase(s.begin());
	ll 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){
	ll x;
	cin >> x;
	cout << c[x] << endl;
}

return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 133 ms 4272 KB Output is correct
4 Correct 134 ms 4344 KB Output is correct
5 Correct 203 ms 11256 KB Output is correct
6 Correct 208 ms 11948 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 21496 KB Output is correct
2 Correct 130 ms 21624 KB Output is correct
3 Correct 346 ms 25560 KB Output is correct
4 Correct 320 ms 25620 KB Output is correct
5 Correct 348 ms 25960 KB Output is correct
6 Correct 335 ms 25976 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 45584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -