oj.uz

Submission #953709

# Submission time Handle Problem Language Result Execution time Memory
953709 2024-03-26T14:16:43 Z Trisanu_Das Arranging Shoes (IOI19_shoes) C++17
0 / 100
 67 ms 134996 KB 
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define ll long long

int n, BIT[100005];
queue<ll> l[100005], r[100005];

void upd(ll val, int idx){
  for(int i = idx; i <= n; i += (i & -i)) BIT[i] += val;
}

ll qry(int idx){
  ll ans = 0;
  for(int i = idx; i > 0; i -= (i & -i)) ans += BIT[i];
  return ans;
}

ll count_swaps(vector<int> s){
  n = s.size();
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    int sz = s[i - 1];
    if(sz < 0){
      sz *= -1;
      if(!r[sz].empty()){
        int need = r[sz].front(); r[sz].pop();
        ans += qry(i) - qry(need - 1);
        upd(1, need);
      }else {
        l[sz].push(i);
        upd(1, i);
      }
    }else{
      if(!l[sz].empty()){
        int need = l[sz].front(); l[sz].pop();
        ans += qry(i) - qry(need - 1);
        upd(1, need);
      }else{
        l[sz].push(i);
        upd(1, i);
      }
    }
  }
  return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 134900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 134900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 134900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 134996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 134900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 134900 KB Output isn't correct
2 Halted 0 ms 0 KB -