Submission #537081

#	Time	Username	Problem	Language	Result	Execution time	Memory
537081		andecaandeci	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	221 ms	146876 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef double db;
#define pairll pair<ll,ll>
#define lpairll pair<pairll,ll>
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define repp(i,a,b) for(ll i = (a); i <= (b); i++)
#define repm(i, a, b) for (ll i = (a); i >= (b); i--)
#define repz(i, a, b) for (ll i = (a); i < (b); i++)
 
const ll MOD = 1e9+7, N = 2e5 + 5, M = 4e5+5, C = 1e5;

ll tc = 1, n, m=0, ar[N], tree[N*4];
string s, ye = "YES", no = "NO";
queue<ll> loc[N];
bool used[N];

void fastt(){ 
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}

ll query(ll nw, ll l, ll r, ll x, ll y){
  if(l > y || r < x) return 0;
  if(l >= x && r <= y) return tree[nw];
  ll mid = (l+r)/2;
  return query(nw*2,l,mid,x,y) + query(nw*2+1,mid+1,r,x,y);
}

void upd(ll nw, ll l, ll r, ll idx){
  if(l == r){
    tree[nw] = 1;
    return;
  }
  ll mid = (l+r)/2;
  if (idx <= mid) upd(nw*2,l,mid,idx);
  else upd (nw*2+1,mid+1,r,idx);
  tree[nw] = tree[nw*2] + tree[nw*2+1]; 
}

ll count_swaps(vector<int> v){
  vector<ll> t;
  ll n = v.size();
  memset(used,0,sizeof(used));
  t.pb(0);
  for (auto i : v) t.pb(i);
  repz(i,1,t.size()){
    loc[t[i]+C].push(i);
  }
  ll ans = 0;
  memset(tree,0,sizeof(tree));
  repz(i,1,t.size()){
    if(used[i]) continue;
    ll ed = (t[i] > 0), nx;
    nx = loc[C-t[i]].front();
    loc[C-t[i]].pop();
    loc[C+t[i]].pop();
    ed += nx-i-1;
    ed -= query(1,1,n,i+1,nx-1);
    upd(1,1,n,nx);
    used[nx] = used[i] = 1;
    ans += ed;
  }

  //cout << ans << endl;
  return ans;
}

// int main(){
//   // freopen("input.txt", "r", stdin);
//   //freopen("output.txt", "w", stdout);
//   fastt();
//   //cin >> tc;
//   while(tc--){
//     cin >> n;
//     vector<ll> v;
//     while(n--){
//       cin >> m;
//       v.pb(m);
//     }
//     cout << count_swaps(v); 
//   }
// }

/*

*/

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:15:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define repz(i, a, b) for (ll i = (a); i < (b); i++)
      |                                          ^
shoes.cpp:54:3: note: in expansion of macro 'repz'
   54 |   repz(i,1,t.size()){
      |   ^~~~
shoes.cpp:15:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define repz(i, a, b) for (ll i = (a); i < (b); i++)
      |                                          ^
shoes.cpp:59:3: note: in expansion of macro 'repz'
   59 |   repz(i,1,t.size()){
      |   ^~~~

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