#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long cnt=0;
const int mn=1e5+100;
vector<queue<int> > poz(mn);
vector<queue<int> > neg(mn);
set<int> skup;
int st[8*mn];
void update(int l,int r,int poz,int tren)
{
if(l==r)
{
st[tren]++;
return;
}
int mid=(l+r)/2;
if(poz<=mid) update(l,mid,poz,2*tren+1);
else update(mid+1,r,poz,2*tren+2);
st[tren]=st[2*tren+1]+st[2*tren+2];
}
int query(int l,int r,int L,int R,int node)
{
if(R<l || r<L) return 0;
if(l<=L && R<=r) return st[node];
int mid=(L+R)/2;
return query(l,r,L,mid,2*node+1)+query(l,r,mid+1,R,2*node+2);
}
void resi(int l,int r,int n,std::vector<int> s)
{
for(l;l<=r;l++)
{
if(l>=r) continue;
int prva=s[l];
if(query(l,l,0,n-1,0)==1) continue;
if(prva>0)
{
poz[prva].pop();
int i=neg[prva].front();
neg[prva].pop();
//cout<<"Obradjujemo pozitivan "<<prva<<endl;
//cout<<i<<endl;
int manji=query(l+1,i,0,n-1,0);
//cout<<"Kveri uradio "<<manji<<endl;
cnt+=(i-l-manji);
//cout<<cnt<<endl;
update(0,n-1,i,0);
//for(int i=0;i<n;i++) cout<<st[i]<<" ";
//cout<<endl;
}
else
{
prva*=-1;
neg[prva].pop();
int i=poz[prva].front();
//cout<<"Obradjujemo negativan "<<prva<<endl;
//cout<<i<<endl;
poz[prva].pop();
int manji=query(l+1,i,0,n-1,0);
//cout<<"Uradio kveri ide gas "<<manji<<endl;
cnt+=(i-(l+1)-manji);
//cout<<cnt<<endl;
update(0,n-1,i,0);
}
}
}
long long count_swaps(std::vector<int> s) {
int n=s.size();
int l=0;
int r=n-1;
for(int i=0;i<s.size();i++)
{
if(s[i]>0) poz[s[i]].push(i);
else neg[-s[i]].push(i);
}
resi(l,r,n,s);
return cnt;
}
Compilation message
shoes.cpp: In function 'void resi(int, int, int, std::vector<int>)':
shoes.cpp:31:9: warning: statement has no effect [-Wunused-value]
31 | for(l;l<=r;l++)
| ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0;i<s.size();i++)
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
134980 KB |
Output is correct |
2 |
Correct |
73 ms |
134996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
134980 KB |
Output is correct |
2 |
Correct |
73 ms |
134996 KB |
Output is correct |
3 |
Correct |
71 ms |
135008 KB |
Output is correct |
4 |
Correct |
70 ms |
134980 KB |
Output is correct |
5 |
Correct |
72 ms |
134972 KB |
Output is correct |
6 |
Correct |
73 ms |
135064 KB |
Output is correct |
7 |
Correct |
71 ms |
135000 KB |
Output is correct |
8 |
Correct |
71 ms |
134980 KB |
Output is correct |
9 |
Correct |
70 ms |
135044 KB |
Output is correct |
10 |
Correct |
72 ms |
134980 KB |
Output is correct |
11 |
Correct |
70 ms |
135076 KB |
Output is correct |
12 |
Correct |
70 ms |
134980 KB |
Output is correct |
13 |
Correct |
70 ms |
134992 KB |
Output is correct |
14 |
Correct |
73 ms |
135048 KB |
Output is correct |
15 |
Correct |
70 ms |
135024 KB |
Output is correct |
16 |
Correct |
71 ms |
134980 KB |
Output is correct |
17 |
Correct |
70 ms |
134960 KB |
Output is correct |
18 |
Correct |
70 ms |
135044 KB |
Output is correct |
19 |
Correct |
71 ms |
135020 KB |
Output is correct |
20 |
Correct |
69 ms |
134980 KB |
Output is correct |
21 |
Correct |
72 ms |
134976 KB |
Output is correct |
22 |
Correct |
70 ms |
134980 KB |
Output is correct |
23 |
Correct |
71 ms |
134964 KB |
Output is correct |
24 |
Correct |
72 ms |
135036 KB |
Output is correct |
25 |
Correct |
71 ms |
135044 KB |
Output is correct |
26 |
Correct |
71 ms |
135016 KB |
Output is correct |
27 |
Correct |
70 ms |
135000 KB |
Output is correct |
28 |
Correct |
70 ms |
135056 KB |
Output is correct |
29 |
Correct |
72 ms |
134964 KB |
Output is correct |
30 |
Correct |
70 ms |
135044 KB |
Output is correct |
31 |
Correct |
71 ms |
135040 KB |
Output is correct |
32 |
Correct |
72 ms |
135080 KB |
Output is correct |
33 |
Correct |
72 ms |
134956 KB |
Output is correct |
34 |
Correct |
71 ms |
134956 KB |
Output is correct |
35 |
Correct |
69 ms |
135012 KB |
Output is correct |
36 |
Correct |
72 ms |
135032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
134980 KB |
Output is correct |
2 |
Correct |
73 ms |
134996 KB |
Output is correct |
3 |
Correct |
84 ms |
135048 KB |
Output is correct |
4 |
Correct |
72 ms |
134980 KB |
Output is correct |
5 |
Correct |
72 ms |
134984 KB |
Output is correct |
6 |
Correct |
71 ms |
134980 KB |
Output is correct |
7 |
Correct |
70 ms |
135008 KB |
Output is correct |
8 |
Correct |
71 ms |
135004 KB |
Output is correct |
9 |
Correct |
73 ms |
134988 KB |
Output is correct |
10 |
Correct |
71 ms |
135004 KB |
Output is correct |
11 |
Correct |
73 ms |
135076 KB |
Output is correct |
12 |
Correct |
70 ms |
134980 KB |
Output is correct |
13 |
Correct |
72 ms |
135048 KB |
Output is correct |
14 |
Correct |
76 ms |
135016 KB |
Output is correct |
15 |
Correct |
71 ms |
135164 KB |
Output is correct |
16 |
Correct |
71 ms |
135124 KB |
Output is correct |
17 |
Correct |
75 ms |
135092 KB |
Output is correct |
18 |
Correct |
75 ms |
135088 KB |
Output is correct |
19 |
Correct |
75 ms |
134988 KB |
Output is correct |
20 |
Correct |
82 ms |
135532 KB |
Output is correct |
21 |
Correct |
83 ms |
135600 KB |
Output is correct |
22 |
Correct |
173 ms |
140280 KB |
Output is correct |
23 |
Correct |
162 ms |
141508 KB |
Output is correct |
24 |
Correct |
170 ms |
141448 KB |
Output is correct |
25 |
Correct |
174 ms |
140256 KB |
Output is correct |
26 |
Correct |
178 ms |
141480 KB |
Output is correct |
27 |
Correct |
158 ms |
141252 KB |
Output is correct |
28 |
Correct |
175 ms |
140708 KB |
Output is correct |
29 |
Correct |
174 ms |
140456 KB |
Output is correct |
30 |
Correct |
177 ms |
140484 KB |
Output is correct |
31 |
Correct |
173 ms |
141632 KB |
Output is correct |
32 |
Correct |
173 ms |
140512 KB |
Output is correct |
33 |
Correct |
174 ms |
140288 KB |
Output is correct |
34 |
Correct |
171 ms |
140524 KB |
Output is correct |
35 |
Correct |
70 ms |
135260 KB |
Output is correct |
36 |
Correct |
73 ms |
135032 KB |
Output is correct |
37 |
Correct |
176 ms |
140676 KB |
Output is correct |
38 |
Correct |
172 ms |
140484 KB |
Output is correct |
39 |
Correct |
172 ms |
140532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
70 ms |
134980 KB |
Output is correct |
2 |
Correct |
71 ms |
135040 KB |
Output is correct |
3 |
Correct |
71 ms |
134964 KB |
Output is correct |
4 |
Correct |
71 ms |
134980 KB |
Output is correct |
5 |
Correct |
207 ms |
138556 KB |
Output is correct |
6 |
Correct |
187 ms |
139736 KB |
Output is correct |
7 |
Correct |
208 ms |
139716 KB |
Output is correct |
8 |
Correct |
171 ms |
140568 KB |
Output is correct |
9 |
Correct |
211 ms |
139716 KB |
Output is correct |
10 |
Correct |
201 ms |
139716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
134980 KB |
Output is correct |
2 |
Correct |
73 ms |
134996 KB |
Output is correct |
3 |
Correct |
71 ms |
135008 KB |
Output is correct |
4 |
Correct |
70 ms |
134980 KB |
Output is correct |
5 |
Correct |
72 ms |
134972 KB |
Output is correct |
6 |
Correct |
73 ms |
135064 KB |
Output is correct |
7 |
Correct |
71 ms |
135000 KB |
Output is correct |
8 |
Correct |
71 ms |
134980 KB |
Output is correct |
9 |
Correct |
70 ms |
135044 KB |
Output is correct |
10 |
Correct |
72 ms |
134980 KB |
Output is correct |
11 |
Correct |
70 ms |
135076 KB |
Output is correct |
12 |
Correct |
70 ms |
134980 KB |
Output is correct |
13 |
Correct |
70 ms |
134992 KB |
Output is correct |
14 |
Correct |
73 ms |
135048 KB |
Output is correct |
15 |
Correct |
70 ms |
135024 KB |
Output is correct |
16 |
Correct |
71 ms |
134980 KB |
Output is correct |
17 |
Correct |
70 ms |
134960 KB |
Output is correct |
18 |
Correct |
70 ms |
135044 KB |
Output is correct |
19 |
Correct |
71 ms |
135020 KB |
Output is correct |
20 |
Correct |
69 ms |
134980 KB |
Output is correct |
21 |
Correct |
72 ms |
134976 KB |
Output is correct |
22 |
Correct |
70 ms |
134980 KB |
Output is correct |
23 |
Correct |
71 ms |
134964 KB |
Output is correct |
24 |
Correct |
72 ms |
135036 KB |
Output is correct |
25 |
Correct |
71 ms |
135044 KB |
Output is correct |
26 |
Correct |
71 ms |
135016 KB |
Output is correct |
27 |
Correct |
70 ms |
135000 KB |
Output is correct |
28 |
Correct |
70 ms |
135056 KB |
Output is correct |
29 |
Correct |
72 ms |
134964 KB |
Output is correct |
30 |
Correct |
70 ms |
135044 KB |
Output is correct |
31 |
Correct |
71 ms |
135040 KB |
Output is correct |
32 |
Correct |
72 ms |
135080 KB |
Output is correct |
33 |
Correct |
72 ms |
134956 KB |
Output is correct |
34 |
Correct |
71 ms |
134956 KB |
Output is correct |
35 |
Correct |
69 ms |
135012 KB |
Output is correct |
36 |
Correct |
72 ms |
135032 KB |
Output is correct |
37 |
Correct |
77 ms |
135068 KB |
Output is correct |
38 |
Correct |
76 ms |
135068 KB |
Output is correct |
39 |
Correct |
76 ms |
134980 KB |
Output is correct |
40 |
Correct |
76 ms |
134980 KB |
Output is correct |
41 |
Correct |
72 ms |
135048 KB |
Output is correct |
42 |
Correct |
72 ms |
135072 KB |
Output is correct |
43 |
Correct |
75 ms |
135076 KB |
Output is correct |
44 |
Correct |
75 ms |
135108 KB |
Output is correct |
45 |
Correct |
73 ms |
135012 KB |
Output is correct |
46 |
Correct |
72 ms |
135028 KB |
Output is correct |
47 |
Correct |
73 ms |
134996 KB |
Output is correct |
48 |
Correct |
71 ms |
135064 KB |
Output is correct |
49 |
Correct |
73 ms |
135092 KB |
Output is correct |
50 |
Correct |
77 ms |
135064 KB |
Output is correct |
51 |
Correct |
74 ms |
135108 KB |
Output is correct |
52 |
Correct |
72 ms |
135044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
134980 KB |
Output is correct |
2 |
Correct |
73 ms |
134996 KB |
Output is correct |
3 |
Correct |
71 ms |
135008 KB |
Output is correct |
4 |
Correct |
70 ms |
134980 KB |
Output is correct |
5 |
Correct |
72 ms |
134972 KB |
Output is correct |
6 |
Correct |
73 ms |
135064 KB |
Output is correct |
7 |
Correct |
71 ms |
135000 KB |
Output is correct |
8 |
Correct |
71 ms |
134980 KB |
Output is correct |
9 |
Correct |
70 ms |
135044 KB |
Output is correct |
10 |
Correct |
72 ms |
134980 KB |
Output is correct |
11 |
Correct |
70 ms |
135076 KB |
Output is correct |
12 |
Correct |
70 ms |
134980 KB |
Output is correct |
13 |
Correct |
70 ms |
134992 KB |
Output is correct |
14 |
Correct |
73 ms |
135048 KB |
Output is correct |
15 |
Correct |
70 ms |
135024 KB |
Output is correct |
16 |
Correct |
71 ms |
134980 KB |
Output is correct |
17 |
Correct |
70 ms |
134960 KB |
Output is correct |
18 |
Correct |
70 ms |
135044 KB |
Output is correct |
19 |
Correct |
71 ms |
135020 KB |
Output is correct |
20 |
Correct |
69 ms |
134980 KB |
Output is correct |
21 |
Correct |
72 ms |
134976 KB |
Output is correct |
22 |
Correct |
70 ms |
134980 KB |
Output is correct |
23 |
Correct |
71 ms |
134964 KB |
Output is correct |
24 |
Correct |
72 ms |
135036 KB |
Output is correct |
25 |
Correct |
71 ms |
135044 KB |
Output is correct |
26 |
Correct |
71 ms |
135016 KB |
Output is correct |
27 |
Correct |
70 ms |
135000 KB |
Output is correct |
28 |
Correct |
70 ms |
135056 KB |
Output is correct |
29 |
Correct |
72 ms |
134964 KB |
Output is correct |
30 |
Correct |
70 ms |
135044 KB |
Output is correct |
31 |
Correct |
71 ms |
135040 KB |
Output is correct |
32 |
Correct |
72 ms |
135080 KB |
Output is correct |
33 |
Correct |
72 ms |
134956 KB |
Output is correct |
34 |
Correct |
71 ms |
134956 KB |
Output is correct |
35 |
Correct |
69 ms |
135012 KB |
Output is correct |
36 |
Correct |
72 ms |
135032 KB |
Output is correct |
37 |
Correct |
84 ms |
135048 KB |
Output is correct |
38 |
Correct |
72 ms |
134980 KB |
Output is correct |
39 |
Correct |
72 ms |
134984 KB |
Output is correct |
40 |
Correct |
71 ms |
134980 KB |
Output is correct |
41 |
Correct |
70 ms |
135008 KB |
Output is correct |
42 |
Correct |
71 ms |
135004 KB |
Output is correct |
43 |
Correct |
73 ms |
134988 KB |
Output is correct |
44 |
Correct |
71 ms |
135004 KB |
Output is correct |
45 |
Correct |
73 ms |
135076 KB |
Output is correct |
46 |
Correct |
70 ms |
134980 KB |
Output is correct |
47 |
Correct |
72 ms |
135048 KB |
Output is correct |
48 |
Correct |
76 ms |
135016 KB |
Output is correct |
49 |
Correct |
71 ms |
135164 KB |
Output is correct |
50 |
Correct |
71 ms |
135124 KB |
Output is correct |
51 |
Correct |
75 ms |
135092 KB |
Output is correct |
52 |
Correct |
75 ms |
135088 KB |
Output is correct |
53 |
Correct |
75 ms |
134988 KB |
Output is correct |
54 |
Correct |
82 ms |
135532 KB |
Output is correct |
55 |
Correct |
83 ms |
135600 KB |
Output is correct |
56 |
Correct |
173 ms |
140280 KB |
Output is correct |
57 |
Correct |
162 ms |
141508 KB |
Output is correct |
58 |
Correct |
170 ms |
141448 KB |
Output is correct |
59 |
Correct |
174 ms |
140256 KB |
Output is correct |
60 |
Correct |
178 ms |
141480 KB |
Output is correct |
61 |
Correct |
158 ms |
141252 KB |
Output is correct |
62 |
Correct |
175 ms |
140708 KB |
Output is correct |
63 |
Correct |
174 ms |
140456 KB |
Output is correct |
64 |
Correct |
177 ms |
140484 KB |
Output is correct |
65 |
Correct |
173 ms |
141632 KB |
Output is correct |
66 |
Correct |
173 ms |
140512 KB |
Output is correct |
67 |
Correct |
174 ms |
140288 KB |
Output is correct |
68 |
Correct |
171 ms |
140524 KB |
Output is correct |
69 |
Correct |
70 ms |
135260 KB |
Output is correct |
70 |
Correct |
73 ms |
135032 KB |
Output is correct |
71 |
Correct |
176 ms |
140676 KB |
Output is correct |
72 |
Correct |
172 ms |
140484 KB |
Output is correct |
73 |
Correct |
172 ms |
140532 KB |
Output is correct |
74 |
Correct |
70 ms |
134980 KB |
Output is correct |
75 |
Correct |
71 ms |
135040 KB |
Output is correct |
76 |
Correct |
71 ms |
134964 KB |
Output is correct |
77 |
Correct |
71 ms |
134980 KB |
Output is correct |
78 |
Correct |
207 ms |
138556 KB |
Output is correct |
79 |
Correct |
187 ms |
139736 KB |
Output is correct |
80 |
Correct |
208 ms |
139716 KB |
Output is correct |
81 |
Correct |
171 ms |
140568 KB |
Output is correct |
82 |
Correct |
211 ms |
139716 KB |
Output is correct |
83 |
Correct |
201 ms |
139716 KB |
Output is correct |
84 |
Correct |
77 ms |
135068 KB |
Output is correct |
85 |
Correct |
76 ms |
135068 KB |
Output is correct |
86 |
Correct |
76 ms |
134980 KB |
Output is correct |
87 |
Correct |
76 ms |
134980 KB |
Output is correct |
88 |
Correct |
72 ms |
135048 KB |
Output is correct |
89 |
Correct |
72 ms |
135072 KB |
Output is correct |
90 |
Correct |
75 ms |
135076 KB |
Output is correct |
91 |
Correct |
75 ms |
135108 KB |
Output is correct |
92 |
Correct |
73 ms |
135012 KB |
Output is correct |
93 |
Correct |
72 ms |
135028 KB |
Output is correct |
94 |
Correct |
73 ms |
134996 KB |
Output is correct |
95 |
Correct |
71 ms |
135064 KB |
Output is correct |
96 |
Correct |
73 ms |
135092 KB |
Output is correct |
97 |
Correct |
77 ms |
135064 KB |
Output is correct |
98 |
Correct |
74 ms |
135108 KB |
Output is correct |
99 |
Correct |
72 ms |
135044 KB |
Output is correct |
100 |
Correct |
72 ms |
135032 KB |
Output is correct |
101 |
Correct |
80 ms |
135616 KB |
Output is correct |
102 |
Correct |
85 ms |
135620 KB |
Output is correct |
103 |
Correct |
237 ms |
140844 KB |
Output is correct |
104 |
Correct |
207 ms |
140740 KB |
Output is correct |
105 |
Correct |
211 ms |
140780 KB |
Output is correct |
106 |
Correct |
204 ms |
139620 KB |
Output is correct |
107 |
Correct |
187 ms |
140808 KB |
Output is correct |
108 |
Correct |
193 ms |
140628 KB |
Output is correct |
109 |
Correct |
175 ms |
140496 KB |
Output is correct |
110 |
Correct |
169 ms |
140580 KB |
Output is correct |
111 |
Correct |
222 ms |
139816 KB |
Output is correct |
112 |
Correct |
225 ms |
140756 KB |
Output is correct |
113 |
Correct |
202 ms |
139700 KB |
Output is correct |
114 |
Correct |
209 ms |
139692 KB |
Output is correct |
115 |
Correct |
212 ms |
139676 KB |
Output is correct |