Submission #950530

#	Time	Username	Problem	Language	Result	Execution time	Memory
950530		qin	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	210 ms	33516 KiB

shoes

#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
struct seg{
		int base;
		vv<int> t;
		void init(int n){
				base = 1;
				while(base < n) base <<= 1;
				t.resize(base<<1, 0);
				for(int i = 1; i <= n; ++i) t[i+base-1] = 1;
				for(int i = base-1; i; --i) t[i] = t[i<<1]+t[i<<1|1];
		}
		void update(int i, int val){
				for(i += base-1, t[i] = val, i >>= 1; i; i >>= 1) t[i] = t[i<<1]+t[i<<1|1];
		}
		int query_interval(int i, int s, int e, int x, int y){
				if(x <= s && e <= y) return t[i];
				int mid = (s+e)>>1, result = 0;
				if(x <= mid) result += query_interval(i<<1, s, mid, x, y);
				if(mid < y) result += query_interval(i<<1|1, mid+1, e, x, y);
				return result;
		}
		int query(int l, int r){
				if(l <= r) return query_interval(1, 1, base, max(1, l), min(base, r));
				return 0;
		}
};
ll count_swaps(vv<int> t){
		int n = ssize(t);
		set<int> s;
		vv<set<int>> v(n+3);
		for(int i = 0; i < n; ++i) t[i] = t[i] > 0 ? 2*t[i]+1 : -2*t[i], s.emplace(i), v[t[i]].emplace(i);
		
		ll result = 0;
		seg seg; seg.init(n+2);
		for(int i = 0; i < n/2; ++i){
				int posx = *s.begin(), x = t[posx];
				int posy = *v[x^1].begin();
				//~ printf("%d: %d %d: ", x, posx, posy);
				if(x & 1) result += seg.query(posx+1, posy);
				else result += seg.query(posx+2, posy);
				seg.update(posx+1, 0), seg.update(posy+1, 0);
				v[x].erase(posx), v[x^1].erase(posy);
				s.erase(posx), s.erase(posy);
				//~ printf("%lld\n", result);
		}
		return result;
}
#ifdef LOCAL
int main(){
		int T = 1;
		for(++T; --T; ){
				int n; scanf("%d", &n);
				vv<int> t(n<<1);
				for(int i = 0; i < n<<1; ++i) scanf("%d", &t[i]);
				ll result = count_swaps(t);
				printf("%lld\n", result);
		}
		return 0;
}
#endif

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15