oj.uz

Submission #332322

# Submission time Handle Problem Language Result Execution time Memory
332322 2020-12-02T03:28:46 Z YJU Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 9000 ms 11488 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e5+5;
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<30);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()



vector<ll> countScans(vector<ll> A,vector<ll> X,vector<ll> V){
	vector<ll> ans;
	ll ma;
	set<ll> cnt[105];
	REP(i,SZ(V))ma=max(ma,V[i]);
	REP(i,SZ(A))ma=max(ma,A[i]);
	if(ma<=100)REP(i,SZ(A))cnt[A[i]].insert(i);
	REP(i,SZ(X)){
		if(ma<=100){
			cnt[A[X[i]]].erase(X[i]);cnt[A[X[i]]=V[i]].insert(X[i]);
			ll res=0,pre=0;
			REP1(j,ma){
				if(SZ(cnt[j])==0)continue;
				res=max(res,*prev(cnt[j].end())-pre-(SZ(cnt[j])-1));
				pre+=SZ(cnt[j]);
			}
			ans.pb(res);
		}else{
			A[X[i]]=V[i];
			vector<pll> a;
			ll res=0;
			REP(j,SZ(A))a.pb(mp(A[j],j));
			sort(a.begin(),a.end());
			REP(j,SZ(a))res=max(res,a[j].second-j);
			ans.pb(res);
		}
	}
	return ans;
}

/*
int main(){
	vector<ll> A,X,V;
	ll n,q,x;
	cin>>n>>q;
	REP(i,n)cin>>x,A.pb(x);
	REP(i,q)cin>>x,X.pb(x),cin>>x,V.pb(x);
	vector<ll> ans=countScans(A,X,V);
	for(ll i:ans)cout<<i<<"\n";
}
//*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 364 KB Output is correct
2 Correct 41 ms 364 KB Output is correct
3 Correct 273 ms 492 KB Output is correct
4 Correct 245 ms 492 KB Output is correct
5 Correct 230 ms 492 KB Output is correct
6 Correct 157 ms 492 KB Output is correct
7 Correct 202 ms 492 KB Output is correct
8 Correct 223 ms 492 KB Output is correct
9 Correct 249 ms 620 KB Output is correct
10 Correct 149 ms 620 KB Output is correct
11 Correct 145 ms 496 KB Output is correct
12 Correct 148 ms 520 KB Output is correct
13 Correct 156 ms 616 KB Output is correct
14 Correct 145 ms 496 KB Output is correct
15 Correct 144 ms 492 KB Output is correct
16 Correct 134 ms 620 KB Output is correct
17 Correct 133 ms 492 KB Output is correct
18 Correct 127 ms 492 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 364 KB Output is correct
2 Correct 41 ms 364 KB Output is correct
3 Correct 273 ms 492 KB Output is correct
4 Correct 245 ms 492 KB Output is correct
5 Correct 230 ms 492 KB Output is correct
6 Correct 157 ms 492 KB Output is correct
7 Correct 202 ms 492 KB Output is correct
8 Correct 223 ms 492 KB Output is correct
9 Correct 249 ms 620 KB Output is correct
10 Correct 149 ms 620 KB Output is correct
11 Correct 145 ms 496 KB Output is correct
12 Correct 148 ms 520 KB Output is correct
13 Correct 156 ms 616 KB Output is correct
14 Correct 145 ms 496 KB Output is correct
15 Correct 144 ms 492 KB Output is correct
16 Correct 134 ms 620 KB Output is correct
17 Correct 133 ms 492 KB Output is correct
18 Correct 127 ms 492 KB Output is correct
19 Correct 3583 ms 1132 KB Output is correct
20 Correct 4769 ms 1004 KB Output is correct
21 Correct 3944 ms 1148 KB Output is correct
22 Correct 4471 ms 1016 KB Output is correct
23 Correct 2719 ms 1004 KB Output is correct
24 Correct 2743 ms 1004 KB Output is correct
25 Correct 2744 ms 1104 KB Output is correct
26 Correct 2857 ms 1012 KB Output is correct
27 Correct 2769 ms 888 KB Output is correct
28 Correct 2702 ms 988 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2028 KB Output is correct
2 Correct 57 ms 3580 KB Output is correct
3 Correct 98 ms 4844 KB Output is correct
4 Correct 93 ms 4844 KB Output is correct
5 Correct 85 ms 4844 KB Output is correct
6 Correct 110 ms 4844 KB Output is correct
7 Correct 83 ms 4844 KB Output is correct
8 Correct 85 ms 4844 KB Output is correct
9 Correct 82 ms 4844 KB Output is correct
10 Correct 80 ms 4844 KB Output is correct
11 Correct 72 ms 4844 KB Output is correct
12 Correct 71 ms 4844 KB Output is correct
13 Correct 67 ms 4844 KB Output is correct
14 Correct 63 ms 4844 KB Output is correct
15 Correct 74 ms 4972 KB Output is correct
16 Correct 57 ms 5064 KB Output is correct
17 Correct 57 ms 4844 KB Output is correct
18 Correct 57 ms 4972 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 364 KB Output is correct
2 Correct 41 ms 364 KB Output is correct
3 Correct 273 ms 492 KB Output is correct
4 Correct 245 ms 492 KB Output is correct
5 Correct 230 ms 492 KB Output is correct
6 Correct 157 ms 492 KB Output is correct
7 Correct 202 ms 492 KB Output is correct
8 Correct 223 ms 492 KB Output is correct
9 Correct 249 ms 620 KB Output is correct
10 Correct 149 ms 620 KB Output is correct
11 Correct 145 ms 496 KB Output is correct
12 Correct 148 ms 520 KB Output is correct
13 Correct 156 ms 616 KB Output is correct
14 Correct 145 ms 496 KB Output is correct
15 Correct 144 ms 492 KB Output is correct
16 Correct 134 ms 620 KB Output is correct
17 Correct 133 ms 492 KB Output is correct
18 Correct 127 ms 492 KB Output is correct
19 Correct 3583 ms 1132 KB Output is correct
20 Correct 4769 ms 1004 KB Output is correct
21 Correct 3944 ms 1148 KB Output is correct
22 Correct 4471 ms 1016 KB Output is correct
23 Correct 2719 ms 1004 KB Output is correct
24 Correct 2743 ms 1004 KB Output is correct
25 Correct 2744 ms 1104 KB Output is correct
26 Correct 2857 ms 1012 KB Output is correct
27 Correct 2769 ms 888 KB Output is correct
28 Correct 2702 ms 988 KB Output is correct
29 Correct 16 ms 2028 KB Output is correct
30 Correct 57 ms 3580 KB Output is correct
31 Correct 98 ms 4844 KB Output is correct
32 Correct 93 ms 4844 KB Output is correct
33 Correct 85 ms 4844 KB Output is correct
34 Correct 110 ms 4844 KB Output is correct
35 Correct 83 ms 4844 KB Output is correct
36 Correct 85 ms 4844 KB Output is correct
37 Correct 82 ms 4844 KB Output is correct
38 Correct 80 ms 4844 KB Output is correct
39 Correct 72 ms 4844 KB Output is correct
40 Correct 71 ms 4844 KB Output is correct
41 Correct 67 ms 4844 KB Output is correct
42 Correct 63 ms 4844 KB Output is correct
43 Correct 74 ms 4972 KB Output is correct
44 Correct 57 ms 5064 KB Output is correct
45 Correct 57 ms 4844 KB Output is correct
46 Correct 57 ms 4972 KB Output is correct
47 Execution timed out 9086 ms 11488 KB Time limit exceeded
48 Halted 0 ms 0 KB -