제출 #792021

#제출 시각아이디문제언어결과실행 시간메모리
792021APROHACKArranging Shoes (IOI19_shoes)C++17
0 / 100
0 ms340 KiB
#include "shoes.h" #include <bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back using namespace std; int nxt[100005][2]; bool past[100005] ; int n; int find_next(int k, int positive){ if(!past[k])return k; if(!past[nxt[k][positive]])return nxt[k][positive]; return nxt[k][positive] = find_next(nxt[k][positive], positive); // siempre tiene que existir. } int bit[100005]; void update(int pos, int val){ pos ++ ; for(; pos <= n ; pos += pos&(-pos)){ bit[pos] += val; } } ll query(int pos){ ll ans = 0; pos ++ ; for(; pos > 0 ; pos -= pos&(-pos)){ ans += bit[pos]; } return ans; } ll getAns(int l, int r){ if(l > r)return 0; if(l > 0)return query(r) - query(l-1); else return query(r); } long long count_swaps(std::vector<int> s) { n = s.size(); for(int i = 0 ; i <=n+2 ; i ++)bit[i] = 0; int siguiente[n][2]; // 0 negative 1 positive for(int i = 0 ; i < n ; i ++)update(i, 1); for(int i = 1 ; i <= n ; i ++){ siguiente[i][0] = -1; siguiente[i][1] = -1; nxt[i][0] = -1; nxt[i][1] = -1; } for(int i = n-1 ; i >= 0 ; i--){ nxt[i][0] = siguiente[abs(s[i])][0]; nxt[i][1] = siguiente[abs(s[i])][1]; if(s[i] > 0)siguiente[abs(s[i])][1] = i; else siguiente[abs(s[i])][0] = i; } memset(past, false, sizeof past); ll ans = 0; for(int i = 0 ; i < n ; i ++){ if(past[i] )continue; int busca = 1; if(s[i] > 0)busca = 0; //cout << "buscando para " << i ; int k = find_next(nxt[i][busca], busca); cout << " desde " << k << endl; ans += getAns(i+1, k-1); //cout << "sumed " << getAns(i+1, k-1); if(busca == 0)ans ++; past[k] = true; past[i] = true; update(k, -1); update(i, -1); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...