답안 #311824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
311824	2020-10-11T20:20:11 Z	MarcoMeijer	Bubble Sort 2 (JOI18_bubblesort2)	C++14	60 / 100	6873 ms	12152 KB

bubblesort2

#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());
 
const int MX=101;
int cnt[MX];

vi countScans(vi A, vi X, vi V){
    int n=A.size();
	int q=X.size();
	vi ans(q);
 
    if(n <= 8000 && q <= 8000) {
        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;
        }
    } else {
        RE(i,n)
            REP(j,A[i],MX)
                cnt[j]++;

        RE(j,q) {
            REP(i,A[X[j]],MX)
                cnt[i]--;
            A[X[j]] = V[j];
            REP(i,A[X[j]],MX)
                cnt[i]++;

            int cAns = 0;
            RE(i,n)
                cAns = max(cAns, i-int(cnt[A[i]] - 1));
            ans[j] = cAns;
        }
    }
 
	return ans;
}

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	384 KB	Output is correct
2	Correct	54 ms	384 KB	Output is correct
3	Correct	346 ms	512 KB	Output is correct
4	Correct	348 ms	512 KB	Output is correct
5	Correct	330 ms	512 KB	Output is correct
6	Correct	255 ms	512 KB	Output is correct
7	Correct	281 ms	632 KB	Output is correct
8	Correct	300 ms	640 KB	Output is correct
9	Correct	322 ms	640 KB	Output is correct
10	Correct	282 ms	632 KB	Output is correct
11	Correct	276 ms	512 KB	Output is correct
12	Correct	276 ms	632 KB	Output is correct
13	Correct	275 ms	512 KB	Output is correct
14	Correct	276 ms	632 KB	Output is correct
15	Correct	274 ms	512 KB	Output is correct
16	Correct	271 ms	512 KB	Output is correct
17	Correct	275 ms	636 KB	Output is correct
18	Correct	276 ms	512 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	384 KB	Output is correct
2	Correct	54 ms	384 KB	Output is correct
3	Correct	346 ms	512 KB	Output is correct
4	Correct	348 ms	512 KB	Output is correct
5	Correct	330 ms	512 KB	Output is correct
6	Correct	255 ms	512 KB	Output is correct
7	Correct	281 ms	632 KB	Output is correct
8	Correct	300 ms	640 KB	Output is correct
9	Correct	322 ms	640 KB	Output is correct
10	Correct	282 ms	632 KB	Output is correct
11	Correct	276 ms	512 KB	Output is correct
12	Correct	276 ms	632 KB	Output is correct
13	Correct	275 ms	512 KB	Output is correct
14	Correct	276 ms	632 KB	Output is correct
15	Correct	274 ms	512 KB	Output is correct
16	Correct	271 ms	512 KB	Output is correct
17	Correct	275 ms	636 KB	Output is correct
18	Correct	276 ms	512 KB	Output is correct
19	Correct	5245 ms	912 KB	Output is correct
20	Correct	6873 ms	980 KB	Output is correct
21	Correct	5301 ms	984 KB	Output is correct
22	Correct	6349 ms	988 KB	Output is correct
23	Correct	5251 ms	992 KB	Output is correct
24	Correct	5279 ms	988 KB	Output is correct
25	Correct	5241 ms	980 KB	Output is correct
26	Correct	5227 ms	896 KB	Output is correct
27	Correct	5250 ms	1144 KB	Output is correct
28	Correct	5267 ms	992 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	632 KB	Output is correct
2	Correct	1203 ms	1164 KB	Output is correct
3	Correct	3048 ms	1784 KB	Output is correct
4	Correct	3052 ms	1784 KB	Output is correct
5	Correct	3072 ms	1784 KB	Output is correct
6	Correct	3044 ms	1748 KB	Output is correct
7	Correct	3041 ms	1912 KB	Output is correct
8	Correct	3053 ms	1656 KB	Output is correct
9	Correct	3078 ms	1748 KB	Output is correct
10	Correct	3056 ms	1752 KB	Output is correct
11	Correct	3060 ms	1784 KB	Output is correct
12	Correct	3062 ms	1752 KB	Output is correct
13	Correct	3048 ms	1784 KB	Output is correct
14	Correct	3058 ms	1784 KB	Output is correct
15	Correct	3054 ms	1744 KB	Output is correct
16	Correct	3069 ms	1664 KB	Output is correct
17	Correct	3081 ms	1792 KB	Output is correct
18	Correct	3058 ms	1784 KB	Output is correct

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	384 KB	Output is correct
2	Correct	54 ms	384 KB	Output is correct
3	Correct	346 ms	512 KB	Output is correct
4	Correct	348 ms	512 KB	Output is correct
5	Correct	330 ms	512 KB	Output is correct
6	Correct	255 ms	512 KB	Output is correct
7	Correct	281 ms	632 KB	Output is correct
8	Correct	300 ms	640 KB	Output is correct
9	Correct	322 ms	640 KB	Output is correct
10	Correct	282 ms	632 KB	Output is correct
11	Correct	276 ms	512 KB	Output is correct
12	Correct	276 ms	632 KB	Output is correct
13	Correct	275 ms	512 KB	Output is correct
14	Correct	276 ms	632 KB	Output is correct
15	Correct	274 ms	512 KB	Output is correct
16	Correct	271 ms	512 KB	Output is correct
17	Correct	275 ms	636 KB	Output is correct
18	Correct	276 ms	512 KB	Output is correct
19	Correct	5245 ms	912 KB	Output is correct
20	Correct	6873 ms	980 KB	Output is correct
21	Correct	5301 ms	984 KB	Output is correct
22	Correct	6349 ms	988 KB	Output is correct
23	Correct	5251 ms	992 KB	Output is correct
24	Correct	5279 ms	988 KB	Output is correct
25	Correct	5241 ms	980 KB	Output is correct
26	Correct	5227 ms	896 KB	Output is correct
27	Correct	5250 ms	1144 KB	Output is correct
28	Correct	5267 ms	992 KB	Output is correct
29	Correct	79 ms	632 KB	Output is correct
30	Correct	1203 ms	1164 KB	Output is correct
31	Correct	3048 ms	1784 KB	Output is correct
32	Correct	3052 ms	1784 KB	Output is correct
33	Correct	3072 ms	1784 KB	Output is correct
34	Correct	3044 ms	1748 KB	Output is correct
35	Correct	3041 ms	1912 KB	Output is correct
36	Correct	3053 ms	1656 KB	Output is correct
37	Correct	3078 ms	1748 KB	Output is correct
38	Correct	3056 ms	1752 KB	Output is correct
39	Correct	3060 ms	1784 KB	Output is correct
40	Correct	3062 ms	1752 KB	Output is correct
41	Correct	3048 ms	1784 KB	Output is correct
42	Correct	3058 ms	1784 KB	Output is correct
43	Correct	3054 ms	1744 KB	Output is correct
44	Correct	3069 ms	1664 KB	Output is correct
45	Correct	3081 ms	1792 KB	Output is correct
46	Correct	3058 ms	1784 KB	Output is correct
47	Runtime error	91 ms	12152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Halted	0 ms	0 KB	-

답안 #311824

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 22.0 / 22.0

Subtask #4 0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
22.0 / 22.0

Subtask #4
0 / 40.0