#include "bits/stdc++.h"
using namespace std;
constexpr int MAXN = 1 << 17;
array<int, MAXN * 2> segTree;
array<queue<int>, MAXN> shoes;
array<bool, MAXN> starts; // true if swapped
array<int, MAXN> linked;
//pos goes from 0
void put(int pos, int val)
{
pos += MAXN;
int diff = val - segTree[pos];
while(pos > 0)
{
segTree[pos] += diff;
pos = pos >> 1;
}
}
//pos from 0, inclusive
int qry(int left, int right)
{
int total = 0;
left += MAXN;
right += MAXN;
while(left < right)
{
if((left & 1) == 1)
{
total += segTree[left];
left++;
}
if((right & 1) == 0)
{
total += segTree[right];
right--;
}
left = left >> 1;
right = right >> 1;
}
if(left == right) total += segTree[left];
return total;
}
long long count_swaps(vector<int> S)
{
segTree.fill(0);
starts.fill(false);
shoes.fill(queue<int>());
linked.fill(-1);
long long total = 0;
for(int i = 0; i < S.size(); i++)
{
int sn = abs(S[i]);
if(shoes[sn].empty())
{
starts[i] = S[i] > 0;
shoes[sn].push(i);
}
else if(S[shoes[sn].front()] + S[i] != 0)
{
starts[i] = S[i] > 0;
shoes[sn].push(i);
}
else
{
//cout << "SHOES[SN]: " << shoes[sn].front() << "\n";
linked[shoes[sn].front()] = i;
total += i - shoes[sn].front();
//cout << "ADD: " << (i - shoes[sn].front()) << "\n";
if(!starts[shoes[sn].front()])
{
//cout << "NOT STARTS\n";
total--;
}
shoes[sn].pop();
}
put(i, S[i] < 0 ? 1 : -1);
}
//cout << "TOTAL PRE PROCESS: " << total << "\n";
for(int ind = 0; ind < S.size(); ind++)
{
if(segTree[MAXN + ind] == 0) continue;
int helps = qry(ind, linked[ind]);
//cout << "HELPS from " << ind << " to " << linked[ind] << ": " << helps << "\n";
total -= helps;
put(ind, 0);
put(linked[ind], 0);
}
return total;
}
/*
int main()
{
int num;
vector<int> vals;
cin >> num;
vals.resize(num);
for(int i = 0; i < num; i++) cin >> vals[i];
cout << count_swaps(vals) << "\n";
}*/
Compilation message
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 0; i < S.size(); i++)
| ~~^~~~~~~~~~
shoes.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int ind = 0; ind < S.size(); ind++)
| ~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
90232 KB |
Output is correct |
2 |
Correct |
72 ms |
90232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
90232 KB |
Output is correct |
2 |
Correct |
72 ms |
90232 KB |
Output is correct |
3 |
Correct |
72 ms |
90232 KB |
Output is correct |
4 |
Correct |
73 ms |
90232 KB |
Output is correct |
5 |
Correct |
74 ms |
90232 KB |
Output is correct |
6 |
Correct |
75 ms |
90232 KB |
Output is correct |
7 |
Incorrect |
74 ms |
90232 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
90232 KB |
Output is correct |
2 |
Correct |
72 ms |
90232 KB |
Output is correct |
3 |
Correct |
71 ms |
90256 KB |
Output is correct |
4 |
Correct |
71 ms |
90188 KB |
Output is correct |
5 |
Correct |
75 ms |
90232 KB |
Output is correct |
6 |
Correct |
75 ms |
90200 KB |
Output is correct |
7 |
Correct |
73 ms |
90232 KB |
Output is correct |
8 |
Correct |
74 ms |
90232 KB |
Output is correct |
9 |
Incorrect |
72 ms |
90232 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
90232 KB |
Output is correct |
2 |
Correct |
79 ms |
90232 KB |
Output is correct |
3 |
Correct |
91 ms |
90232 KB |
Output is correct |
4 |
Correct |
73 ms |
90232 KB |
Output is correct |
5 |
Runtime error |
272 ms |
187048 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
90232 KB |
Output is correct |
2 |
Correct |
72 ms |
90232 KB |
Output is correct |
3 |
Correct |
72 ms |
90232 KB |
Output is correct |
4 |
Correct |
73 ms |
90232 KB |
Output is correct |
5 |
Correct |
74 ms |
90232 KB |
Output is correct |
6 |
Correct |
75 ms |
90232 KB |
Output is correct |
7 |
Incorrect |
74 ms |
90232 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
90232 KB |
Output is correct |
2 |
Correct |
72 ms |
90232 KB |
Output is correct |
3 |
Correct |
72 ms |
90232 KB |
Output is correct |
4 |
Correct |
73 ms |
90232 KB |
Output is correct |
5 |
Correct |
74 ms |
90232 KB |
Output is correct |
6 |
Correct |
75 ms |
90232 KB |
Output is correct |
7 |
Incorrect |
74 ms |
90232 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |