oj.uz

Submission #294937

# Submission time Handle Problem Language Result Execution time Memory
294937 2020-09-09T10:55:12 Z Fasho Arranging Shoes (IOI19_shoes) C++14
100 / 100
 493 ms 419368 KB 
#include <bits/stdc++.h>
#define N 200005
#define ll long long int
#define fo(i,x,y)	for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#include "shoes.h"
using namespace std;
 
ll n,m,ar[N],sum,tree[4*N],lazy[4*N],mark[N],tutmac[N][3],tut[N];
 
stack<int> st[N][3];
 
void build(int ind,int l,int r)
{
	if(l==r)
	{
		tree[ind]=l;
		return;
	}
	int mid=(l+r)/2;
	build(ind*2,l,mid);
	build(ind*2+1,mid+1,r);
}
 
void push(int ind,int l,int r)
{
	ll x=lazy[ind];
	lazy[ind]=0;
	tree[ind]+=x;
	if(l==r)
		return;
	lazy[ind*2]+=x;
	lazy[ind*2+1]+=x;
}
 
ll query(int ind,int l,int r,int a)
{
	if(l>a || r<a)
		return 0;
	push(ind,l,r);
	if(l==r)
		return tree[ind];
	int mid=(l+r)/2;
	if(a<=mid)
		return query(ind*2,l,mid,a);
	else
		return query(ind*2+1,mid+1,r,a);
}
void upd(int ind,int l,int r,int a,int b)
{
	if(l>b || r<a)
		return;
	push(ind,l,r);
	if(l>=a && r<=b)
	{
		lazy[ind]++;
		push(ind,l,r);
		return;
	}
	int mid=(l+r)/2;
	upd(ind*2,l,mid,a,b);
	upd(ind*2+1,mid+1,r,a,b);
}
 
void pre()
{
	for(int i=n;i>=1;i--)
	{
		if(ar[i]<0)
			st[-ar[i]][0].push(i);
		else
			st[ar[i]][1].push(i);
	}
 
}
 
long long count_swaps(std::vector<int> s) {
	n=s.size();
	fo(i,1,n)
		ar[i]=s[i-1];
	pre();
	build(1,1,n);
	
 
	// cout<<query(1,1,n,7)<<endl;
	// upd(1,1,n,1,6);
	// upd(1,1,n,2,4);
	// cout<<query(1,1,n,7)<<endl;
	// cout<<endl;	
 
	fo(i,1,n)
	{
		if(mark[i])
			continue;
		mark[i]=1;
 
		if(ar[i]>0)
		{
			while(mark[st[ar[i]][0].top()])
				st[ar[i]][0].pop();
			ll x=st[ar[i]][0].top();
			mark[x]=1;
			ll a=query(1,1,n,i);
			ll b=query(1,1,n,x);
			sum+=b-a;
			// cerr<<i<<sp<<x<<sp<<a<<sp<<b<<endl;
			upd(1,1,n,i,x-1);
		}
		else
		{
			while(mark[st[-ar[i]][1].top()])
				st[-ar[i]][1].pop();
			ll x=st[-ar[i]][1].top();
			mark[x]=1;
			ll a=query(1,1,n,i);
			ll b=query(1,1,n,x);
			sum+=b-a-1;
			// cerr<<i<<sp<<x<<sp<<a<<sp<<b<<endl;
			upd(1,1,n,i,x-1);
 
		}
		
	}
 
	return sum;
}
// int main() {
// 	int n;
// 	assert(1 == scanf("%d", &n));
// 	vector<int> S(2 * n);
// 	for (int i = 0; i < 2 * n; i++)
// 		assert(1 == scanf("%d", &S[i]));
// 	fclose(stdin);
 
// 	long long result = count_swaps(S);
 
// 	printf("%lld\n", result);
// 	fclose(stdout);
// 	return 0;
// }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 404416 KB Output is correct
2 Correct 301 ms 404216 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 404416 KB Output is correct
2 Correct 301 ms 404216 KB Output is correct
3 Correct 301 ms 404432 KB Output is correct
4 Correct 301 ms 404216 KB Output is correct
5 Correct 307 ms 404348 KB Output is correct
6 Correct 305 ms 404216 KB Output is correct
7 Correct 308 ms 404216 KB Output is correct
8 Correct 302 ms 404344 KB Output is correct
9 Correct 303 ms 404344 KB Output is correct
10 Correct 306 ms 404344 KB Output is correct
11 Correct 305 ms 404344 KB Output is correct
12 Correct 303 ms 404216 KB Output is correct
13 Correct 310 ms 404344 KB Output is correct
14 Correct 301 ms 404276 KB Output is correct
15 Correct 304 ms 404216 KB Output is correct
16 Correct 308 ms 404216 KB Output is correct
17 Correct 310 ms 404292 KB Output is correct
18 Correct 304 ms 404344 KB Output is correct
19 Correct 301 ms 404344 KB Output is correct
20 Correct 303 ms 404300 KB Output is correct
21 Correct 304 ms 404220 KB Output is correct
22 Correct 302 ms 404216 KB Output is correct
23 Correct 310 ms 404216 KB Output is correct
24 Correct 297 ms 404308 KB Output is correct
25 Correct 303 ms 404216 KB Output is correct
26 Correct 303 ms 404344 KB Output is correct
27 Correct 302 ms 404272 KB Output is correct
28 Correct 319 ms 404376 KB Output is correct
29 Correct 323 ms 404220 KB Output is correct
30 Correct 312 ms 404344 KB Output is correct
31 Correct 314 ms 404216 KB Output is correct
32 Correct 310 ms 404344 KB Output is correct
33 Correct 305 ms 404344 KB Output is correct
34 Correct 312 ms 404216 KB Output is correct
35 Correct 311 ms 404216 KB Output is correct
36 Correct 310 ms 404216 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 404416 KB Output is correct
2 Correct 301 ms 404216 KB Output is correct
3 Correct 321 ms 404252 KB Output is correct
4 Correct 304 ms 404320 KB Output is correct
5 Correct 314 ms 404336 KB Output is correct
6 Correct 307 ms 404296 KB Output is correct
7 Correct 313 ms 404368 KB Output is correct
8 Correct 309 ms 404216 KB Output is correct
9 Correct 315 ms 404324 KB Output is correct
10 Correct 308 ms 404216 KB Output is correct
11 Correct 318 ms 404332 KB Output is correct
12 Correct 307 ms 404308 KB Output is correct
13 Correct 308 ms 404344 KB Output is correct
14 Correct 306 ms 404216 KB Output is correct
15 Correct 313 ms 404216 KB Output is correct
16 Correct 319 ms 404296 KB Output is correct
17 Correct 309 ms 404472 KB Output is correct
18 Correct 334 ms 404344 KB Output is correct
19 Correct 338 ms 404368 KB Output is correct
20 Correct 349 ms 405996 KB Output is correct
21 Correct 346 ms 405880 KB Output is correct
22 Correct 417 ms 419052 KB Output is correct
23 Correct 417 ms 419324 KB Output is correct
24 Correct 419 ms 419088 KB Output is correct
25 Correct 430 ms 419092 KB Output is correct
26 Correct 420 ms 419256 KB Output is correct
27 Correct 418 ms 419176 KB Output is correct
28 Correct 438 ms 419320 KB Output is correct
29 Correct 418 ms 419320 KB Output is correct
30 Correct 420 ms 419320 KB Output is correct
31 Correct 439 ms 419088 KB Output is correct
32 Correct 423 ms 419296 KB Output is correct
33 Correct 416 ms 419064 KB Output is correct
34 Correct 427 ms 419368 KB Output is correct
35 Correct 334 ms 404216 KB Output is correct
36 Correct 313 ms 404360 KB Output is correct
37 Correct 414 ms 419272 KB Output is correct
38 Correct 435 ms 419320 KB Output is correct
39 Correct 418 ms 419264 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 404216 KB Output is correct
2 Correct 319 ms 404268 KB Output is correct
3 Correct 308 ms 404344 KB Output is correct
4 Correct 322 ms 404316 KB Output is correct
5 Correct 457 ms 418380 KB Output is correct
6 Correct 456 ms 418400 KB Output is correct
7 Correct 484 ms 418424 KB Output is correct
8 Correct 427 ms 419320 KB Output is correct
9 Correct 468 ms 418368 KB Output is correct
10 Correct 465 ms 418388 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 404416 KB Output is correct
2 Correct 301 ms 404216 KB Output is correct
3 Correct 301 ms 404432 KB Output is correct
4 Correct 301 ms 404216 KB Output is correct
5 Correct 307 ms 404348 KB Output is correct
6 Correct 305 ms 404216 KB Output is correct
7 Correct 308 ms 404216 KB Output is correct
8 Correct 302 ms 404344 KB Output is correct
9 Correct 303 ms 404344 KB Output is correct
10 Correct 306 ms 404344 KB Output is correct
11 Correct 305 ms 404344 KB Output is correct
12 Correct 303 ms 404216 KB Output is correct
13 Correct 310 ms 404344 KB Output is correct
14 Correct 301 ms 404276 KB Output is correct
15 Correct 304 ms 404216 KB Output is correct
16 Correct 308 ms 404216 KB Output is correct
17 Correct 310 ms 404292 KB Output is correct
18 Correct 304 ms 404344 KB Output is correct
19 Correct 301 ms 404344 KB Output is correct
20 Correct 303 ms 404300 KB Output is correct
21 Correct 304 ms 404220 KB Output is correct
22 Correct 302 ms 404216 KB Output is correct
23 Correct 310 ms 404216 KB Output is correct
24 Correct 297 ms 404308 KB Output is correct
25 Correct 303 ms 404216 KB Output is correct
26 Correct 303 ms 404344 KB Output is correct
27 Correct 302 ms 404272 KB Output is correct
28 Correct 319 ms 404376 KB Output is correct
29 Correct 323 ms 404220 KB Output is correct
30 Correct 312 ms 404344 KB Output is correct
31 Correct 314 ms 404216 KB Output is correct
32 Correct 310 ms 404344 KB Output is correct
33 Correct 305 ms 404344 KB Output is correct
34 Correct 312 ms 404216 KB Output is correct
35 Correct 311 ms 404216 KB Output is correct
36 Correct 310 ms 404216 KB Output is correct
37 Correct 318 ms 404256 KB Output is correct
38 Correct 311 ms 404216 KB Output is correct
39 Correct 311 ms 404216 KB Output is correct
40 Correct 326 ms 404424 KB Output is correct
41 Correct 311 ms 404344 KB Output is correct
42 Correct 306 ms 404428 KB Output is correct
43 Correct 314 ms 404392 KB Output is correct
44 Correct 304 ms 404344 KB Output is correct
45 Correct 309 ms 404472 KB Output is correct
46 Correct 305 ms 404344 KB Output is correct
47 Correct 307 ms 404344 KB Output is correct
48 Correct 307 ms 404344 KB Output is correct
49 Correct 305 ms 404344 KB Output is correct
50 Correct 329 ms 404472 KB Output is correct
51 Correct 331 ms 404344 KB Output is correct
52 Correct 311 ms 404344 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 404416 KB Output is correct
2 Correct 301 ms 404216 KB Output is correct
3 Correct 301 ms 404432 KB Output is correct
4 Correct 301 ms 404216 KB Output is correct
5 Correct 307 ms 404348 KB Output is correct
6 Correct 305 ms 404216 KB Output is correct
7 Correct 308 ms 404216 KB Output is correct
8 Correct 302 ms 404344 KB Output is correct
9 Correct 303 ms 404344 KB Output is correct
10 Correct 306 ms 404344 KB Output is correct
11 Correct 305 ms 404344 KB Output is correct
12 Correct 303 ms 404216 KB Output is correct
13 Correct 310 ms 404344 KB Output is correct
14 Correct 301 ms 404276 KB Output is correct
15 Correct 304 ms 404216 KB Output is correct
16 Correct 308 ms 404216 KB Output is correct
17 Correct 310 ms 404292 KB Output is correct
18 Correct 304 ms 404344 KB Output is correct
19 Correct 301 ms 404344 KB Output is correct
20 Correct 303 ms 404300 KB Output is correct
21 Correct 304 ms 404220 KB Output is correct
22 Correct 302 ms 404216 KB Output is correct
23 Correct 310 ms 404216 KB Output is correct
24 Correct 297 ms 404308 KB Output is correct
25 Correct 303 ms 404216 KB Output is correct
26 Correct 303 ms 404344 KB Output is correct
27 Correct 302 ms 404272 KB Output is correct
28 Correct 319 ms 404376 KB Output is correct
29 Correct 323 ms 404220 KB Output is correct
30 Correct 312 ms 404344 KB Output is correct
31 Correct 314 ms 404216 KB Output is correct
32 Correct 310 ms 404344 KB Output is correct
33 Correct 305 ms 404344 KB Output is correct
34 Correct 312 ms 404216 KB Output is correct
35 Correct 311 ms 404216 KB Output is correct
36 Correct 310 ms 404216 KB Output is correct
37 Correct 321 ms 404252 KB Output is correct
38 Correct 304 ms 404320 KB Output is correct
39 Correct 314 ms 404336 KB Output is correct
40 Correct 307 ms 404296 KB Output is correct
41 Correct 313 ms 404368 KB Output is correct
42 Correct 309 ms 404216 KB Output is correct
43 Correct 315 ms 404324 KB Output is correct
44 Correct 308 ms 404216 KB Output is correct
45 Correct 318 ms 404332 KB Output is correct
46 Correct 307 ms 404308 KB Output is correct
47 Correct 308 ms 404344 KB Output is correct
48 Correct 306 ms 404216 KB Output is correct
49 Correct 313 ms 404216 KB Output is correct
50 Correct 319 ms 404296 KB Output is correct
51 Correct 309 ms 404472 KB Output is correct
52 Correct 334 ms 404344 KB Output is correct
53 Correct 338 ms 404368 KB Output is correct
54 Correct 349 ms 405996 KB Output is correct
55 Correct 346 ms 405880 KB Output is correct
56 Correct 417 ms 419052 KB Output is correct
57 Correct 417 ms 419324 KB Output is correct
58 Correct 419 ms 419088 KB Output is correct
59 Correct 430 ms 419092 KB Output is correct
60 Correct 420 ms 419256 KB Output is correct
61 Correct 418 ms 419176 KB Output is correct
62 Correct 438 ms 419320 KB Output is correct
63 Correct 418 ms 419320 KB Output is correct
64 Correct 420 ms 419320 KB Output is correct
65 Correct 439 ms 419088 KB Output is correct
66 Correct 423 ms 419296 KB Output is correct
67 Correct 416 ms 419064 KB Output is correct
68 Correct 427 ms 419368 KB Output is correct
69 Correct 334 ms 404216 KB Output is correct
70 Correct 313 ms 404360 KB Output is correct
71 Correct 414 ms 419272 KB Output is correct
72 Correct 435 ms 419320 KB Output is correct
73 Correct 418 ms 419264 KB Output is correct
74 Correct 333 ms 404216 KB Output is correct
75 Correct 319 ms 404268 KB Output is correct
76 Correct 308 ms 404344 KB Output is correct
77 Correct 322 ms 404316 KB Output is correct
78 Correct 457 ms 418380 KB Output is correct
79 Correct 456 ms 418400 KB Output is correct
80 Correct 484 ms 418424 KB Output is correct
81 Correct 427 ms 419320 KB Output is correct
82 Correct 468 ms 418368 KB Output is correct
83 Correct 465 ms 418388 KB Output is correct
84 Correct 318 ms 404256 KB Output is correct
85 Correct 311 ms 404216 KB Output is correct
86 Correct 311 ms 404216 KB Output is correct
87 Correct 326 ms 404424 KB Output is correct
88 Correct 311 ms 404344 KB Output is correct
89 Correct 306 ms 404428 KB Output is correct
90 Correct 314 ms 404392 KB Output is correct
91 Correct 304 ms 404344 KB Output is correct
92 Correct 309 ms 404472 KB Output is correct
93 Correct 305 ms 404344 KB Output is correct
94 Correct 307 ms 404344 KB Output is correct
95 Correct 307 ms 404344 KB Output is correct
96 Correct 305 ms 404344 KB Output is correct
97 Correct 329 ms 404472 KB Output is correct
98 Correct 331 ms 404344 KB Output is correct
99 Correct 311 ms 404344 KB Output is correct
100 Correct 307 ms 404476 KB Output is correct
101 Correct 322 ms 405880 KB Output is correct
102 Correct 318 ms 405880 KB Output is correct
103 Correct 493 ms 418680 KB Output is correct
104 Correct 421 ms 418424 KB Output is correct
105 Correct 444 ms 418424 KB Output is correct
106 Correct 453 ms 418552 KB Output is correct
107 Correct 419 ms 418424 KB Output is correct
108 Correct 418 ms 418424 KB Output is correct
109 Correct 411 ms 419320 KB Output is correct
110 Correct 417 ms 419320 KB Output is correct
111 Correct 451 ms 418424 KB Output is correct
112 Correct 471 ms 418424 KB Output is correct
113 Correct 474 ms 418556 KB Output is correct
114 Correct 456 ms 418432 KB Output is correct
115 Correct 450 ms 418424 KB Output is correct