Submission #1193404

#TimeUsernameProblemLanguageResultExecution timeMemory
1193404yoshiArranging Shoes (IOI19_shoes)C++20
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define ss second #define ff first using namespace std; ll df[1234567],ans; vector<ll> vv[1234567]; struct segtree{ ll n; vector<ll>d; segtree(ll n){ d.resize(4*n); build(1,1,n); } void build(ll v, ll l, ll r){ if(l == r){ d[v] = 1; return; } ll m = (l+r)/2; build(v*2,l,m); build(v*2+1,m+1,r); d[v] = d[v*2]+d[v*2+1]; } void update(ll v,ll l, ll r, ll pos, ll val){ if(pos < l or pos > r)return; if(l == r){ d[v] = val; return; } ll m = (l+r)/2; update(v*2,l,m,pos,val); update(v*2+1,m+1,r,pos,val); d[v] = d[v*2]+d[v*2+1]; } ll query(ll v, ll l, ll r, ll L, ll R){ if(R<L||R<l||r<L) return 0ll; if(L<=l&&r<=R) return d[v]; ll m = (l+r)/2; return query(v*2,l,m,L,R) + query(v*2+1,m+1,r,L,R); } }; int count_swaps(vector<int> a){ int n = a.size() / 2; map<int, vector<int>> w; for(int i = 0; i < a.size(); ++i){ w[a[i]].push_back(i + 1); } vector<pair<int,int>> v; int cnt = 0; for(auto& [key, vec] : w){ if(key < 0) continue; auto& left = w[-key]; auto& right = w[key]; for(int i = 0; i < left.size(); ++i){ if(left[i] < right[i]){ v.push_back({left[i] + 1, right[i] - 1}); } else { v.push_back({right[i] + 1, left[i] - 1}); cnt++; } } } sort(v.begin(), v.end()); segtree yo(2 * n); for(auto [l, r] : v){ cnt += yo.query(1, 1, 2*n, l, r); yo.update(1, 1, 2*n, r + 1, 0); } return cnt; } int main(){ int n; cin>>n; vector<int>v(2*n); for(int i=0;i<2*n;i++){ cin>>v[i]; } cout<<count_swaps(v); }

Compilation message (stderr)

/usr/bin/ld: /tmp/cc736NJH.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc5jNpbm.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status