Submission #295019

#	Time	Username	Problem	Language	Result	Execution time	Memory
295019		AKaan37	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	802 ms	361524 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t;
lo cev,tree[li*4],lazy[li*4];
map<lo,lo> mpp;
queue<lo> q[li];
string s;

inline void push(int node,int start,int end){
	if(lazy[node]==0)return;
	tree[node]+=(lazy[node]*(end-start+1));
	if(start!=end){
		lazy[node*2]+=lazy[node];
		lazy[node*2+1]+=lazy[node];
	}
	lazy[node]=0;
}

inline void update(int node,int start,int end,int l,int r){
	push(node,start,end);
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){
		lazy[node]++;
		push(node,start,end);
		return ;
	}
	update(node*2,start,mid,l,r),update(node*2+1,mid+1,end,l,r);
	tree[node]=tree[node*2]+tree[node*2+1];
}

inline lo query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	push(node,start,end);
	if(start>=l && end<=r)return tree[node];
	return query(node*2,start,mid,l,r)+query(node*2+1,mid+1,end,l,r);
}

long long count_swaps(std::vector<int> v) {
	vector<int> vv;
	vv.pb(0);
	for(int i=0;i<(int)v.size();i++)vv.pb(v[i]);
	v=vv;
	n=200000;
	for(int i=1;i<(int)v.size();i++){
		if(mpp[-v[i]]){
			mpp[-v[i]]--;
			if(v[i]>0){
				int ind=q[abs(v[i])].front();
				q[abs(v[i])].pop();
				cev+=(i+(query(1,1,n,i,i))-(ind+query(1,1,n,ind,ind)))-1;
				update(1,1,n,ind+1,i);
			}
			else{
				int ind=q[abs(v[i])].front();
				q[abs(v[i])].pop();
				cev+=(i+(query(1,1,n,i,i))-(ind+query(1,1,n,ind,ind)));
				update(1,1,n,ind,i);
			}
		}
		else{
			mpp[v[i]]++;
			q[abs(v[i])].push(i);
		}
	}
	return cev;
}

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