답안 #97791 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97791	2019-02-18T13:45:42 Z	Alexa2001	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3018 ms	46304 KB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

#define left_son (node<<1)
#define right_son ((node<<1)|1)

using namespace std;

const int Nmax = 1e6 + 5, lim = 1e6, inf = 1e6;
typedef long long ll;

ll a[Nmax], val[Nmax];

class SegmentTree
{
    int lazy[Nmax<<2], a[Nmax<<2];

public:
    void add(int node, int st, int dr, int L, int R, int Add)
    {
        if(L <= st && dr <= R)
        {
            lazy[node] += Add;
            return;
        }

        int mid = (st+dr) >> 1;
        if(L <= mid) add(left_son, st, mid, L, R, Add);
        if(mid < R) add(right_son, mid+1, dr, L, R, Add);

        a[node] = max(a[left_son] + lazy[left_son], a[right_son] + lazy[right_son]);
    }
    int query()
    {
        return a[1] + lazy[1];
    }
    void init(int node, int st, int dr)
    {
        a[node] = -inf; lazy[node] = 0;
        if(st == dr) return;
        int mid = (st+dr) >> 1;
        init(left_son, st, mid); init(right_son, mid+1, dr);
    }

} aint;

int Search(vector<ll> &a, ll val)
{
    int st = 0, dr = a.size() - 1;
    while(st <= dr)
    {
        int mid = (st+dr) >> 1;
        if(a[mid] < val) st = mid+1;
            else dr = mid-1;
    }
    return st + 1;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
    int N = A.size(), i;
    int Q = V.size();

    for(i=0; i<N; ++i) a[i] = (ll) lim * A[i] + i;
    for(i=0; i<Q; ++i) val[i] = (ll) lim * V[i] + X[i];

    vector<ll> vals;
    for(i=0; i<N; ++i) vals.push_back(a[i]);
    for(i=0; i<Q; ++i) vals.push_back(val[i]);
    sort(vals.begin(), vals.end());

    int cnt = vals.size();
    aint.init(1, 1, cnt);

    for(i=0; i<N; ++i)
    {
        int pos = Search(vals, (a[i]));
        aint.add(1, 1, cnt, pos, pos, +inf+i);
        aint.add(1, 1, cnt, 1, pos, +1);
    }

    vector<int> answer(Q);
    for(i=0; i<Q; ++i)
    {
        int pos = Search(vals, a[X[i]]);
        aint.add(1, 1, cnt, 1, pos, -1);
        aint.add(1, 1, cnt, pos, pos, -inf-X[i]);

        a[X[i]] = val[i];
        int act = Search(vals, val[i]);
        aint.add(1, 1, cnt, act, act, +inf+X[i]);
        aint.add(1, 1, cnt, 1, act, 1);

        answer[i] = aint.query() - N;
    }
    return answer;
}

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	4 ms	512 KB	Output is correct
3	Correct	6 ms	512 KB	Output is correct
4	Correct	6 ms	640 KB	Output is correct
5	Correct	7 ms	640 KB	Output is correct
6	Correct	6 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	640 KB	Output is correct
9	Correct	8 ms	512 KB	Output is correct
10	Correct	7 ms	512 KB	Output is correct
11	Correct	6 ms	512 KB	Output is correct
12	Correct	6 ms	512 KB	Output is correct
13	Correct	8 ms	640 KB	Output is correct
14	Correct	8 ms	640 KB	Output is correct
15	Correct	6 ms	512 KB	Output is correct
16	Correct	6 ms	512 KB	Output is correct
17	Correct	8 ms	512 KB	Output is correct
18	Correct	7 ms	640 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	4 ms	512 KB	Output is correct
3	Correct	6 ms	512 KB	Output is correct
4	Correct	6 ms	640 KB	Output is correct
5	Correct	7 ms	640 KB	Output is correct
6	Correct	6 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	640 KB	Output is correct
9	Correct	8 ms	512 KB	Output is correct
10	Correct	7 ms	512 KB	Output is correct
11	Correct	6 ms	512 KB	Output is correct
12	Correct	6 ms	512 KB	Output is correct
13	Correct	8 ms	640 KB	Output is correct
14	Correct	8 ms	640 KB	Output is correct
15	Correct	6 ms	512 KB	Output is correct
16	Correct	6 ms	512 KB	Output is correct
17	Correct	8 ms	512 KB	Output is correct
18	Correct	7 ms	640 KB	Output is correct
19	Correct	17 ms	1152 KB	Output is correct
20	Correct	23 ms	1152 KB	Output is correct
21	Correct	27 ms	1152 KB	Output is correct
22	Correct	20 ms	1152 KB	Output is correct
23	Correct	18 ms	1196 KB	Output is correct
24	Correct	17 ms	1152 KB	Output is correct
25	Correct	26 ms	1152 KB	Output is correct
26	Correct	17 ms	1152 KB	Output is correct
27	Correct	17 ms	1152 KB	Output is correct
28	Correct	18 ms	1152 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	1788 KB	Output is correct
2	Correct	77 ms	3192 KB	Output is correct
3	Correct	162 ms	5484 KB	Output is correct
4	Correct	152 ms	5356 KB	Output is correct
5	Correct	156 ms	5332 KB	Output is correct
6	Correct	195 ms	5356 KB	Output is correct
7	Correct	134 ms	5356 KB	Output is correct
8	Correct	154 ms	5488 KB	Output is correct
9	Correct	145 ms	5356 KB	Output is correct
10	Correct	138 ms	5356 KB	Output is correct
11	Correct	140 ms	5400 KB	Output is correct
12	Correct	144 ms	5356 KB	Output is correct
13	Correct	111 ms	5356 KB	Output is correct
14	Correct	106 ms	5328 KB	Output is correct
15	Correct	120 ms	5360 KB	Output is correct
16	Correct	105 ms	5356 KB	Output is correct
17	Correct	106 ms	5356 KB	Output is correct
18	Correct	112 ms	5488 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	4 ms	512 KB	Output is correct
3	Correct	6 ms	512 KB	Output is correct
4	Correct	6 ms	640 KB	Output is correct
5	Correct	7 ms	640 KB	Output is correct
6	Correct	6 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	640 KB	Output is correct
9	Correct	8 ms	512 KB	Output is correct
10	Correct	7 ms	512 KB	Output is correct
11	Correct	6 ms	512 KB	Output is correct
12	Correct	6 ms	512 KB	Output is correct
13	Correct	8 ms	640 KB	Output is correct
14	Correct	8 ms	640 KB	Output is correct
15	Correct	6 ms	512 KB	Output is correct
16	Correct	6 ms	512 KB	Output is correct
17	Correct	8 ms	512 KB	Output is correct
18	Correct	7 ms	640 KB	Output is correct
19	Correct	17 ms	1152 KB	Output is correct
20	Correct	23 ms	1152 KB	Output is correct
21	Correct	27 ms	1152 KB	Output is correct
22	Correct	20 ms	1152 KB	Output is correct
23	Correct	18 ms	1196 KB	Output is correct
24	Correct	17 ms	1152 KB	Output is correct
25	Correct	26 ms	1152 KB	Output is correct
26	Correct	17 ms	1152 KB	Output is correct
27	Correct	17 ms	1152 KB	Output is correct
28	Correct	18 ms	1152 KB	Output is correct
29	Correct	26 ms	1788 KB	Output is correct
30	Correct	77 ms	3192 KB	Output is correct
31	Correct	162 ms	5484 KB	Output is correct
32	Correct	152 ms	5356 KB	Output is correct
33	Correct	156 ms	5332 KB	Output is correct
34	Correct	195 ms	5356 KB	Output is correct
35	Correct	134 ms	5356 KB	Output is correct
36	Correct	154 ms	5488 KB	Output is correct
37	Correct	145 ms	5356 KB	Output is correct
38	Correct	138 ms	5356 KB	Output is correct
39	Correct	140 ms	5400 KB	Output is correct
40	Correct	144 ms	5356 KB	Output is correct
41	Correct	111 ms	5356 KB	Output is correct
42	Correct	106 ms	5328 KB	Output is correct
43	Correct	120 ms	5360 KB	Output is correct
44	Correct	105 ms	5356 KB	Output is correct
45	Correct	106 ms	5356 KB	Output is correct
46	Correct	112 ms	5488 KB	Output is correct
47	Correct	591 ms	17176 KB	Output is correct
48	Correct	2640 ms	43992 KB	Output is correct
49	Correct	3018 ms	46260 KB	Output is correct
50	Correct	2813 ms	46244 KB	Output is correct
51	Correct	2633 ms	46244 KB	Output is correct
52	Correct	2689 ms	46240 KB	Output is correct
53	Correct	2829 ms	46076 KB	Output is correct
54	Correct	2436 ms	46256 KB	Output is correct
55	Correct	2796 ms	46292 KB	Output is correct
56	Correct	2731 ms	46256 KB	Output is correct
57	Correct	2764 ms	46292 KB	Output is correct
58	Correct	2531 ms	46292 KB	Output is correct
59	Correct	2137 ms	46292 KB	Output is correct
60	Correct	2184 ms	46164 KB	Output is correct
61	Correct	2397 ms	46304 KB	Output is correct
62	Correct	2212 ms	46164 KB	Output is correct
63	Correct	2027 ms	46156 KB	Output is correct
64	Correct	2113 ms	46264 KB	Output is correct
65	Correct	1924 ms	46164 KB	Output is correct
66	Correct	1973 ms	46276 KB	Output is correct
67	Correct	2095 ms	46164 KB	Output is correct

답안 #97791

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 22.0 / 22.0

Subtask #4 40.0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
22.0 / 22.0

Subtask #4
40.0 / 40.0