제출 #989801

#제출 시각아이디문제언어결과실행 시간메모리
989801mateuszwesArranging Shoes (IOI19_shoes)C++17
100 / 100
50 ms21840 KiB
#include <bits/stdc++.h> #define F first #define S second #define pb push_back typedef long long ll; typedef unsigned long long ull; using namespace std; #include "shoes.h" constexpr int base = 1<<19; constexpr int debug = 0; constexpr ll mini = -1e18-7; constexpr int N = 3e5+7; constexpr int M = 1e5+7; vector<int> shoe_index[N]; int ind[N]; bool istaken[N]; ll tree[2*base+7]; //delta do indeksu void add(int a, int b, ll val){ a += base-1; b += base+1; while(a/2 != b/2){ if(!(a&1)){ tree[a+1] += val; } a /= 2; if(b&1){ tree[b-1] += val; } b /= 2; } } ll query(int v){ ll ans = 0; v += base; while(v > 0){ ans += tree[v]; v /= 2; } return ans; } ll count_swaps(vector<int> s){ ll ans = 0; for(int i = 0; i < s.size(); i++){ shoe_index[s[i]+M].pb(i); } for(int i = 0; i < s.size(); i++){ if(istaken[i]) continue; istaken[i] = 1; int index = shoe_index[-s[i]+M][ind[-s[i]+M]]; istaken[index] = 1; if(s[i] < 0) ans--; ans += (index+query(index)-(i+query(i))); if(debug) cout << i << ' ' << index << ' ' << ans << ' ' << query(i) << ' ' << query(index) << endl; add(index, s.size(), -1); ind[s[i]+M]++; ind[-s[i]+M]++; } return ans; }

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

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