제출 #151669

#제출 시각아이디문제언어결과실행 시간메모리
151669ae04071Arranging Shoes (IOI19_shoes)C++14
100 / 100
530 ms22912 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; using lli = long long; using pii = pair<int,int>; int n; struct seg_tr{ int tr[200001]; void init() { for(int i=0;i<=n;i++) tr[i] = 0; } void upd(int cur, int val) { while(cur<=n) tr[cur]+=val, cur+=cur&-cur; } int get(int cur) { int ret=0; while(cur) ret+=tr[cur], cur-=cur&-cur; return ret; } }seg; long long count_swaps(vector<int> s) { set<pii> vi, iv; n = s.size(); seg.init(); for(int i=0;i<s.size();i++) { vi.insert({s[i], i}); iv.insert({i, s[i]}); seg.upd(i+1, 1); } lli ans = 0; int n=s.size() / 2; for(int i=0;i<n;i++) { auto st = iv.begin(); auto mat = vi.lower_bound({-st->se, 0}); ans += seg.get(mat->se); if(st->se < 0) ans--; seg.upd(st->fi+1, -1); seg.upd(mat->se+1, -1); iv.erase({mat->se, -st->se}); vi.erase(mat); vi.erase({st->se, st->fi}); iv.erase(st); } return ans; }

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     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...