Submission #723310

#TimeUsernameProblemLanguageResultExecution timeMemory
723310josiftepeArranging Shoes (IOI19_shoes)C++14
45 / 100
468 ms152036 KiB
#include <iostream> #include <fstream> #include <vector> #include <map> #include <queue> #include "shoes.h" using namespace std; typedef long long ll; const int maxn = 2e5 + 10; ll segment_tree[3 * maxn]; void build_tree(int L, int R, int position) { if(L == R) { segment_tree[position] = 0; } else { int middle = (L + R) / 2; build_tree(L, middle, 2 * position); build_tree(middle + 1, R, 2 * position + 1); segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1]; } } // L R i L R j L R ll query(int L, int R, int position, int i, int j) { if(i <= L and R <= j) { return segment_tree[position]; } if(R < i or j < L) { return 0; } int middle = (L + R) / 2; return query(L, middle, 2 * position, i, j) + query(middle + 1, R, 2 * position + 1, i, j); } void update(int L, int R, int position, int idx, ll new_val) { if(L == R) { segment_tree[position] += new_val; return; } int middle = (L + R) / 2; if(idx <= middle) { update(L, middle, 2 * position, idx, new_val); } else { update(middle + 1, R, 2 * position + 1, idx, new_val); } segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1]; } ll count_swaps(vector<int> v) { map<int, queue<int> > m; vector<int> S; int cnt = 0; for(int i = 0; i < v.size(); i++) { if(!m[v[i]].empty()) { S.push_back(m[v[i]].front()); m[v[i]].pop(); } else { int r = 0; if(v[i] > 0) { r = 1; } S.push_back(2 * cnt + r); m[-v[i]].push(2 * cnt + (1 - r)); cnt++; } } build_tree(0, v.size(), 1); ll res = 0; for(int i = 0; i < S.size(); i++) { update(0, v.size(), 1, S[i], 1); res += query(0, v.size(), 1, i + 1, v.size()); } return res; }

Compilation message (stderr)

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