제출 #759523

#제출 시각아이디문제언어결과실행 시간메모리
759523KN200711Arranging Shoes (IOI19_shoes)C++14
100 / 100
61 ms16412 KiB
#include "shoes.h" # include <bits/stdc++.h> # define ll long long using namespace std; const int MXN = 2e5; vector<int> lf[100001], rg[100001]; int idx[2][100001]; int fen[200001], pl[200001]; void add(int a, int p) { while(a <= MXN) { fen[a] += p; a += a & (-a); } return; } int qry(int a) { int res = 0; while(a > 0) { res += fen[a]; a -= a&(-a); } return res; } ll count_swaps(vector<int> s) { for(int i=1;i<=1e5;i++) { lf[i].clear(); rg[i].clear(); idx[0][i] = idx[1][i] = 0; fen[2 * i] = fen[2 * i - 1] = 0; pl[2 * i - 1] = pl[2 * i] = 0; } for(int i=0;i<s.size();i++) { add(i+1, 1); if(s[i] < 0) lf[-s[i]].push_back(i + 1); else rg[s[i]].push_back(i + 1); } int N = s.size(); ll ans = 0ll; for(int i=1;i<=N;i++) { if(pl[i]) continue; // cout<<i<<endl; int S = s[i - 1]; if(S < 0) { // cari pasangannya int P = rg[-S][idx[1][-S]]; pl[P] = 1; idx[1][-S]++; idx[0][-S]++; int ix = qry(P); ans += (1ll * ix - 1ll * 2); add(P, -1); add(i, -1); } else { int P = lf[S][idx[0][S]]; pl[P] = 1; idx[0][S]++; idx[1][S]++; int ix = qry(P); ans += (1ll * ix - 1ll * 1); add(P, -1); add(i, -1); } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<s.size();i++) {
      |              ~^~~~~~~~~
#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...