답안 #77085 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77085	2018-09-20T21:44:42 Z	duality	Bubble Sort 2 (JOI18_bubblesort2)	C++11	100 / 100	3562 ms	309832 KB

bubblesort2

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include "bubblesort2.h"

vpii sorted,sorted2;
int tree[1 << 21],lazy[1 << 21];
int prop(int s,int e,int i) {
    tree[i] += lazy[i];
    if (s != e) lazy[2*i+1] += lazy[i],lazy[2*i+2] += lazy[i];
    lazy[i] = 0;
    return 0;
}
int update(int s,int e,int as,int ae,int i,int num,int f) {
    prop(s,e,i);
    if ((s > ae) || (e < as)) return tree[i];
    else if ((s >= as) && (e <= ae)) {
        if (f) tree[i] = num;
        else lazy[i] = num;
        prop(s,e,i);
        return tree[i];
    }

    int mid = (s+e) / 2;
    tree[i] = max(update(s,mid,as,ae,2*i+1,num,f),update(mid+1,e,as,ae,2*i+2,num,f));
    return tree[i];
}
int bit[1000001];
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V) {
    int i,j;
    vi ans;
    for (i = 0; i < A.size(); i++) sorted.pb(mp(A[i],i)),sorted2.pb(mp(A[i],i));
    for (i = 0; i < X.size(); i++) sorted.pb(mp(V[i],X[i]));
    sort(sorted.begin(),sorted.end());
    sorted.resize(unique(sorted.begin(),sorted.end())-sorted.begin());
    sort(sorted2.begin(),sorted2.end());
    for (i = 0; i < A.size(); i++) {
        int p = lower_bound(sorted2.begin(),sorted2.end(),mp(A[i],i))-sorted2.begin();
        int q = lower_bound(sorted.begin(),sorted.end(),mp(A[i],i))-sorted.begin();
        update(0,sorted.size()-1,q,q,0,i-p,1);
        for (j = q+1; j <= sorted.size(); j += j & (-j)) bit[j]++;
    }
    for (i = 0; i < X.size(); i++) {
        int p = lower_bound(sorted.begin(),sorted.end(),mp(A[X[i]],X[i]))-sorted.begin();
        update(0,sorted.size()-1,p,p,0,-MAX_VAL,1);
        update(0,sorted.size()-1,p+1,sorted.size()-1,0,1,0);
        for (j = p+1; j <= sorted.size(); j += j & (-j)) bit[j]--;
        A[X[i]] = V[i];
        p = lower_bound(sorted.begin(),sorted.end(),mp(V[i],X[i]))-sorted.begin();
        int x = 0;
        for (j = p+1; j > 0; j -= j & (-j)) x += bit[j];
        update(0,sorted.size()-1,p,p,0,X[i]-x,1);
        update(0,sorted.size()-1,p+1,sorted.size()-1,0,-1,0);
        for (j = p+1; j <= sorted.size(); j += j & (-j)) bit[j]++;
        ans.pb(tree[0]+lazy[0]);
    }
    return ans;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < A.size(); i++) sorted.pb(mp(A[i],i)),sorted2.pb(mp(A[i],i));
                 ~~^~~~~~~~~~
bubblesort2.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < X.size(); i++) sorted.pb(mp(V[i],X[i]));
                 ~~^~~~~~~~~~
bubblesort2.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < A.size(); i++) {
                 ~~^~~~~~~~~~
bubblesort2.cpp:94:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = q+1; j <= sorted.size(); j += j & (-j)) bit[j]++;
                       ~~^~~~~~~~~~~~~~~~
bubblesort2.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < X.size(); i++) {
                 ~~^~~~~~~~~~
bubblesort2.cpp:100:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = p+1; j <= sorted.size(); j += j & (-j)) bit[j]--;
                       ~~^~~~~~~~~~~~~~~~
bubblesort2.cpp:107:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = p+1; j <= sorted.size(); j += j & (-j)) bit[j]++;
                       ~~^~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	4 ms	524 KB	Output is correct
3	Correct	7 ms	748 KB	Output is correct
4	Correct	7 ms	828 KB	Output is correct
5	Correct	8 ms	876 KB	Output is correct
6	Correct	7 ms	908 KB	Output is correct
7	Correct	8 ms	1036 KB	Output is correct
8	Correct	7 ms	1200 KB	Output is correct
9	Correct	7 ms	1280 KB	Output is correct
10	Correct	7 ms	1280 KB	Output is correct
11	Correct	7 ms	1292 KB	Output is correct
12	Correct	7 ms	1392 KB	Output is correct
13	Correct	7 ms	1560 KB	Output is correct
14	Correct	7 ms	1700 KB	Output is correct
15	Correct	7 ms	1700 KB	Output is correct
16	Correct	7 ms	1700 KB	Output is correct
17	Correct	7 ms	1704 KB	Output is correct
18	Correct	7 ms	1740 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	4 ms	524 KB	Output is correct
3	Correct	7 ms	748 KB	Output is correct
4	Correct	7 ms	828 KB	Output is correct
5	Correct	8 ms	876 KB	Output is correct
6	Correct	7 ms	908 KB	Output is correct
7	Correct	8 ms	1036 KB	Output is correct
8	Correct	7 ms	1200 KB	Output is correct
9	Correct	7 ms	1280 KB	Output is correct
10	Correct	7 ms	1280 KB	Output is correct
11	Correct	7 ms	1292 KB	Output is correct
12	Correct	7 ms	1392 KB	Output is correct
13	Correct	7 ms	1560 KB	Output is correct
14	Correct	7 ms	1700 KB	Output is correct
15	Correct	7 ms	1700 KB	Output is correct
16	Correct	7 ms	1700 KB	Output is correct
17	Correct	7 ms	1704 KB	Output is correct
18	Correct	7 ms	1740 KB	Output is correct
19	Correct	24 ms	2428 KB	Output is correct
20	Correct	27 ms	2724 KB	Output is correct
21	Correct	26 ms	2916 KB	Output is correct
22	Correct	26 ms	3112 KB	Output is correct
23	Correct	25 ms	3308 KB	Output is correct
24	Correct	27 ms	3468 KB	Output is correct
25	Correct	25 ms	3636 KB	Output is correct
26	Correct	33 ms	3796 KB	Output is correct
27	Correct	28 ms	3956 KB	Output is correct
28	Correct	24 ms	4088 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	4904 KB	Output is correct
2	Correct	110 ms	6588 KB	Output is correct
3	Correct	200 ms	9452 KB	Output is correct
4	Correct	200 ms	9980 KB	Output is correct
5	Correct	188 ms	10540 KB	Output is correct
6	Correct	211 ms	11216 KB	Output is correct
7	Correct	195 ms	11952 KB	Output is correct
8	Correct	193 ms	12276 KB	Output is correct
9	Correct	216 ms	13040 KB	Output is correct
10	Correct	163 ms	13040 KB	Output is correct
11	Correct	163 ms	13068 KB	Output is correct
12	Correct	158 ms	13680 KB	Output is correct
13	Correct	160 ms	14300 KB	Output is correct
14	Correct	170 ms	14928 KB	Output is correct
15	Correct	155 ms	15556 KB	Output is correct
16	Correct	153 ms	16204 KB	Output is correct
17	Correct	148 ms	16836 KB	Output is correct
18	Correct	156 ms	17508 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	4 ms	524 KB	Output is correct
3	Correct	7 ms	748 KB	Output is correct
4	Correct	7 ms	828 KB	Output is correct
5	Correct	8 ms	876 KB	Output is correct
6	Correct	7 ms	908 KB	Output is correct
7	Correct	8 ms	1036 KB	Output is correct
8	Correct	7 ms	1200 KB	Output is correct
9	Correct	7 ms	1280 KB	Output is correct
10	Correct	7 ms	1280 KB	Output is correct
11	Correct	7 ms	1292 KB	Output is correct
12	Correct	7 ms	1392 KB	Output is correct
13	Correct	7 ms	1560 KB	Output is correct
14	Correct	7 ms	1700 KB	Output is correct
15	Correct	7 ms	1700 KB	Output is correct
16	Correct	7 ms	1700 KB	Output is correct
17	Correct	7 ms	1704 KB	Output is correct
18	Correct	7 ms	1740 KB	Output is correct
19	Correct	24 ms	2428 KB	Output is correct
20	Correct	27 ms	2724 KB	Output is correct
21	Correct	26 ms	2916 KB	Output is correct
22	Correct	26 ms	3112 KB	Output is correct
23	Correct	25 ms	3308 KB	Output is correct
24	Correct	27 ms	3468 KB	Output is correct
25	Correct	25 ms	3636 KB	Output is correct
26	Correct	33 ms	3796 KB	Output is correct
27	Correct	28 ms	3956 KB	Output is correct
28	Correct	24 ms	4088 KB	Output is correct
29	Correct	35 ms	4904 KB	Output is correct
30	Correct	110 ms	6588 KB	Output is correct
31	Correct	200 ms	9452 KB	Output is correct
32	Correct	200 ms	9980 KB	Output is correct
33	Correct	188 ms	10540 KB	Output is correct
34	Correct	211 ms	11216 KB	Output is correct
35	Correct	195 ms	11952 KB	Output is correct
36	Correct	193 ms	12276 KB	Output is correct
37	Correct	216 ms	13040 KB	Output is correct
38	Correct	163 ms	13040 KB	Output is correct
39	Correct	163 ms	13068 KB	Output is correct
40	Correct	158 ms	13680 KB	Output is correct
41	Correct	160 ms	14300 KB	Output is correct
42	Correct	170 ms	14928 KB	Output is correct
43	Correct	155 ms	15556 KB	Output is correct
44	Correct	153 ms	16204 KB	Output is correct
45	Correct	148 ms	16836 KB	Output is correct
46	Correct	156 ms	17508 KB	Output is correct
47	Correct	768 ms	35260 KB	Output is correct
48	Correct	2938 ms	74596 KB	Output is correct
49	Correct	3198 ms	90036 KB	Output is correct
50	Correct	3562 ms	102792 KB	Output is correct
51	Correct	3327 ms	115684 KB	Output is correct
52	Correct	3211 ms	128600 KB	Output is correct
53	Correct	3225 ms	141648 KB	Output is correct
54	Correct	2878 ms	154596 KB	Output is correct
55	Correct	3092 ms	167736 KB	Output is correct
56	Correct	2903 ms	180764 KB	Output is correct
57	Correct	3105 ms	193596 KB	Output is correct
58	Correct	2825 ms	206836 KB	Output is correct
59	Correct	2624 ms	218088 KB	Output is correct
60	Correct	2685 ms	229704 KB	Output is correct
61	Correct	2665 ms	241456 KB	Output is correct
62	Correct	2558 ms	252760 KB	Output is correct
63	Correct	2630 ms	264336 KB	Output is correct
64	Correct	2537 ms	275864 KB	Output is correct
65	Correct	2451 ms	287096 KB	Output is correct
66	Correct	2410 ms	298268 KB	Output is correct
67	Correct	2402 ms	309832 KB	Output is correct

답안 #77085

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