oj.uz

Submission #705743

# Submission time Handle Problem Language Result Execution time Memory
705743 2023-03-05T05:13:30 Z myrcella Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 1 ms 316 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,a,b) for (int i=(a);i<(b);i++)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define pq priority_queue
#define debug(x) cerr<<#x<<"="<<x<<"\n"

const int maxn = 2e5+10;
int n;

int ans[maxn];
set <int> a,b;

int main() {
	cin.tie(0);
	cin>>n;
	rep(i,1,n+1) a.insert(i),b.insert(i);
	ll ans = 0;
	rep(i,0,2*n) {
		int x,y;
		cin>>x>>y;
		int dif1 = 2e9+10,val1;
		int dif2 = 2e9+10,val2;
		set<int>::iterator it = lower_bound(ALL(a),x);
		if (it!=a.end() and ((*it)-x)<dif1) val1 = *it, dif1 = val1-x;
		if (it!=a.begin() and (x-(*(--it)))<dif1) val1 = *it, dif1 = x - val1;
		it = lower_bound(ALL(b),x);
		if (it!=b.end() and ((*it)-x)<dif2) val2 = *it, dif2 = val2-x;
		if (it!=b.begin() and (x-(*(--it)))<dif2) val2 = *it, dif2 = x - val2;
		
		if (dif1+abs(y-1)<dif2+abs(y-2)) {
			a.erase(val1);
			ans += dif1+abs(y-1);
			debug(val1),debug(1);
		}
		else {
			b.erase(val2);
			ans += dif2+abs(y-2);
			debug(val2),debug(2);
		}
		debug(ans);
	}
	cout<<ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -