oj.uz

Submission #311821

# Submission time Handle Problem Language Result Execution time Memory
311821 2020-10-11T20:14:12 Z MarcoMeijer Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 9000 ms 3064 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vi countScans(vi A, vi X, vi V){
    int n=A.size();
	int q=X.size();
	vi ans(q);

    multiset<int> ms;
    RE(i,n) ms.insert(A[i]);
    vi B(n,0);
    RE(j,q) {
        ms.erase(ms.find(A[X[j]]));
        A[X[j]] = V[j];
        ms.insert(V[j]);

        int ci=0;
        FOR(i,ms) B[ci++]=i;

        int cAns = 0;
        RE(i,n)
            cAns = max(cAns, i-int(upper_bound(all(B), A[i])-B.begin() - 1));
        ans[j] = cAns;
    }

	return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 54 ms 384 KB Output is correct
3 Correct 351 ms 512 KB Output is correct
4 Correct 350 ms 512 KB Output is correct
5 Correct 325 ms 512 KB Output is correct
6 Correct 249 ms 512 KB Output is correct
7 Correct 279 ms 632 KB Output is correct
8 Correct 299 ms 512 KB Output is correct
9 Correct 325 ms 512 KB Output is correct
10 Correct 273 ms 512 KB Output is correct
11 Correct 274 ms 512 KB Output is correct
12 Correct 274 ms 512 KB Output is correct
13 Correct 273 ms 512 KB Output is correct
14 Correct 276 ms 632 KB Output is correct
15 Correct 274 ms 632 KB Output is correct
16 Correct 273 ms 632 KB Output is correct
17 Correct 274 ms 632 KB Output is correct
18 Correct 269 ms 632 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 54 ms 384 KB Output is correct
3 Correct 351 ms 512 KB Output is correct
4 Correct 350 ms 512 KB Output is correct
5 Correct 325 ms 512 KB Output is correct
6 Correct 249 ms 512 KB Output is correct
7 Correct 279 ms 632 KB Output is correct
8 Correct 299 ms 512 KB Output is correct
9 Correct 325 ms 512 KB Output is correct
10 Correct 273 ms 512 KB Output is correct
11 Correct 274 ms 512 KB Output is correct
12 Correct 274 ms 512 KB Output is correct
13 Correct 273 ms 512 KB Output is correct
14 Correct 276 ms 632 KB Output is correct
15 Correct 274 ms 632 KB Output is correct
16 Correct 273 ms 632 KB Output is correct
17 Correct 274 ms 632 KB Output is correct
18 Correct 269 ms 632 KB Output is correct
19 Correct 5281 ms 908 KB Output is correct
20 Correct 6978 ms 984 KB Output is correct
21 Correct 5287 ms 1180 KB Output is correct
22 Correct 6430 ms 1184 KB Output is correct
23 Correct 5202 ms 1144 KB Output is correct
24 Correct 5207 ms 1144 KB Output is correct
25 Correct 5236 ms 1144 KB Output is correct
26 Correct 5232 ms 1144 KB Output is correct
27 Correct 5222 ms 1144 KB Output is correct
28 Correct 5243 ms 1144 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6418 ms 2040 KB Output is correct
2 Execution timed out 9012 ms 3064 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 54 ms 384 KB Output is correct
3 Correct 351 ms 512 KB Output is correct
4 Correct 350 ms 512 KB Output is correct
5 Correct 325 ms 512 KB Output is correct
6 Correct 249 ms 512 KB Output is correct
7 Correct 279 ms 632 KB Output is correct
8 Correct 299 ms 512 KB Output is correct
9 Correct 325 ms 512 KB Output is correct
10 Correct 273 ms 512 KB Output is correct
11 Correct 274 ms 512 KB Output is correct
12 Correct 274 ms 512 KB Output is correct
13 Correct 273 ms 512 KB Output is correct
14 Correct 276 ms 632 KB Output is correct
15 Correct 274 ms 632 KB Output is correct
16 Correct 273 ms 632 KB Output is correct
17 Correct 274 ms 632 KB Output is correct
18 Correct 269 ms 632 KB Output is correct
19 Correct 5281 ms 908 KB Output is correct
20 Correct 6978 ms 984 KB Output is correct
21 Correct 5287 ms 1180 KB Output is correct
22 Correct 6430 ms 1184 KB Output is correct
23 Correct 5202 ms 1144 KB Output is correct
24 Correct 5207 ms 1144 KB Output is correct
25 Correct 5236 ms 1144 KB Output is correct
26 Correct 5232 ms 1144 KB Output is correct
27 Correct 5222 ms 1144 KB Output is correct
28 Correct 5243 ms 1144 KB Output is correct
29 Correct 6418 ms 2040 KB Output is correct
30 Execution timed out 9012 ms 3064 KB Time limit exceeded
31 Halted 0 ms 0 KB -