Submission #367731

#	Time	Username	Problem	Language	Result	Execution time	Memory
367731		CSQ31	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	127 ms	17888 KiB

shoes

#pragma GCC optimize("Ofast") 
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
struct fenwick{
	ll n;
	vector<ll>bit;
	void upd(ll pos,ll val){
		for(int i=pos;i<=n;i+=i&(-i))bit[i]+=val;
	}
	ll query(ll r){
		ll res = 0;
		for(int i=r;i>0;i-=i&(-i))res+=bit[i];
	    return res;
	}
	void init(vector<ll>a){
		for(int i=1;i<=n;i++){
			bit[i]+=a[i];
			int j = i + (i&(-i));
			if(j<=n)bit[j]+=bit[i];
		}
	}
	int search(ll val){
		ll sum = 0,pos = 0;
		for(int i=19;i>=0;i--){
			if(pos+(1<<i) < n && sum+bit[pos+(1<<i)]<val){
				pos+=(1<<i);
				sum+=bit[pos];
			}
		}
		return pos+1;
	}
	fenwick(int _n){
		n = _n;
		bit.resize(n+1);
	}
};
long long count_swaps(std::vector<int> s) {
	int n = sz(s)/2;
	vii l(n+1),r(n+1);
	for(int i=0;i<2*n;i++){
		if(s[i] < 0)l[-s[i]].pb(i);
		else r[s[i]].pb(i);
	}
	vector<int>pos(2*n+1);
	vector<pair<int,pii>>shoe;
	for(int i=1;i<=n;i++){
		for(int j=0;j<sz(l[i]);j++){
			shoe.pb({l[i][j] + r[i][j],{l[i][j],r[i][j]}});
			
		}
	}
	sort(all(shoe));
	int cnt = 1;
	for(auto x:shoe){
		int a = x.se.fi;
		int b = x.se.se;
		pos[a] = cnt;
		pos[b] = cnt+1;
		cnt+=2;
	}
	ll ans = 0;
	fenwick val(2*n+1);
	for(int i=0;i<2*n;i++){
		ans+=val.query(2*n) - val.query(pos[i]);
		val.upd(pos[i],1);
	}
	return ans;
}

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