답안 #58374 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58374	2018-07-17T15:16:40 Z	Benq	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	6710 ms	111696 KB

bubblesort2

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

template<class T, int SZ> struct LazySegTree {
    T sum[2*SZ], mx[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
    
    LazySegTree() {
        F0R(i,2*SZ) mx[i] = -MOD, sum[i] = 0;
        memset (lazy,0,sizeof lazy);
    }
    
    void push(int ind, int L, int R) {
        mx[ind] += lazy[ind];
        if (L != R) lazy[2*ind] += lazy[ind], lazy[2*ind+1] += lazy[ind];
        lazy[ind] = 0;
    }
    
    void pull(int ind) {
        sum[ind] = sum[2*ind]+sum[2*ind+1];
        mx[ind] = max(mx[2*ind],mx[2*ind+1]);
    }
    
    void build() {
        F0Rd(i,SZ) pull(i);
    }
    
    T qsum(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (lo > R || L > hi) return 0;
        if (lo <= L && R <= hi) return sum[ind];
        
        int M = (L+R)/2;
        return qsum(lo,hi,2*ind,L,M) + qsum(lo,hi,2*ind+1,M+1,R);
    }

    T qmax(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (lo > R || L > hi) return -MOD;
        if (lo <= L && R <= hi) return mx[ind];
        
        int M = (L+R)/2;
        return max(qmax(lo,hi,2*ind,L,M), qmax(lo,hi,2*ind+1,M+1,R));
    }
    
    void se(int pos, pi val, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (R < pos || pos < L) return;
        if (L == R) {
            mx[ind] = val.f, sum[ind] = val.s;
            return;
        }
        int M = (L+R)/2;
        se(pos,val,2*ind,L,M), se(pos,val,2*ind+1,M+1,R);
        pull(ind);
    }
    
    void upd(int lo, int hi, int inc, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (hi < L || R < lo) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = inc;
            push(ind,L,R);
            return;
        }
        
        int M = (L+R)/2;
        upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
        pull(ind);
    }
};

LazySegTree<int,1<<20> L;

#include "bubblesort2.h"
map<pi,int> m;
vpi v; 
vi cur;

void init(vi A, vi X, vi V) {
    F0R(i,sz(A)) {
        m[{A[i],i}] = 0;
        v.pb({A[i],i});
    }
    F0R(i,sz(V)) m[{V[i],X[i]}] = 0;
    int co = 0;
    for (auto& a: m) a.s = co++;
    sort(all(v));
    
    cur = A;
    F0R(i,sz(v)) {
        int ind = m[v[i]];
        L.mx[ind^(1<<20)] = v[i].s-i;
        L.sum[ind^(1<<20)] = 1;
    }
    
    L.build();
}

// // store current pos - correct pos based on {value, correct pos}

int process(int x, int v) {
    int pos = m[{cur[x],x}];
    L.upd(pos+1,(1<<20)-1,1);
    L.se(pos,{-MOD,0});
    
    cur[x] = v;
    
    pos = m[{cur[x],x}];
    L.upd(pos+1,(1<<20)-1,-1);
    L.se(pos,{x-L.qsum(0,pos-1),1});
    
    return L.qmax(0,(1<<20)-1);
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    init(A,X,V);
    vi answer; F0R(i,sz(V)) answer.pb(process(X[i],V[i]));
	return answer;
}

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	24952 KB	Output is correct
2	Correct	32 ms	25196 KB	Output is correct
3	Correct	32 ms	25380 KB	Output is correct
4	Correct	40 ms	25424 KB	Output is correct
5	Correct	47 ms	25444 KB	Output is correct
6	Correct	34 ms	25540 KB	Output is correct
7	Correct	36 ms	25552 KB	Output is correct
8	Correct	42 ms	25644 KB	Output is correct
9	Correct	31 ms	25644 KB	Output is correct
10	Correct	29 ms	25644 KB	Output is correct
11	Correct	44 ms	25644 KB	Output is correct
12	Correct	30 ms	25644 KB	Output is correct
13	Correct	31 ms	25644 KB	Output is correct
14	Correct	44 ms	25644 KB	Output is correct
15	Correct	42 ms	25644 KB	Output is correct
16	Correct	45 ms	25644 KB	Output is correct
17	Correct	39 ms	25644 KB	Output is correct
18	Correct	36 ms	25644 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	24952 KB	Output is correct
2	Correct	32 ms	25196 KB	Output is correct
3	Correct	32 ms	25380 KB	Output is correct
4	Correct	40 ms	25424 KB	Output is correct
5	Correct	47 ms	25444 KB	Output is correct
6	Correct	34 ms	25540 KB	Output is correct
7	Correct	36 ms	25552 KB	Output is correct
8	Correct	42 ms	25644 KB	Output is correct
9	Correct	31 ms	25644 KB	Output is correct
10	Correct	29 ms	25644 KB	Output is correct
11	Correct	44 ms	25644 KB	Output is correct
12	Correct	30 ms	25644 KB	Output is correct
13	Correct	31 ms	25644 KB	Output is correct
14	Correct	44 ms	25644 KB	Output is correct
15	Correct	42 ms	25644 KB	Output is correct
16	Correct	45 ms	25644 KB	Output is correct
17	Correct	39 ms	25644 KB	Output is correct
18	Correct	36 ms	25644 KB	Output is correct
19	Correct	63 ms	26416 KB	Output is correct
20	Correct	73 ms	26668 KB	Output is correct
21	Correct	78 ms	26668 KB	Output is correct
22	Correct	74 ms	26796 KB	Output is correct
23	Correct	54 ms	26796 KB	Output is correct
24	Correct	66 ms	26796 KB	Output is correct
25	Correct	53 ms	26796 KB	Output is correct
26	Correct	52 ms	26796 KB	Output is correct
27	Correct	51 ms	26796 KB	Output is correct
28	Correct	67 ms	26796 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	27816 KB	Output is correct
2	Correct	185 ms	30884 KB	Output is correct
3	Correct	390 ms	33880 KB	Output is correct
4	Correct	419 ms	33892 KB	Output is correct
5	Correct	347 ms	33892 KB	Output is correct
6	Correct	349 ms	33892 KB	Output is correct
7	Correct	404 ms	33892 KB	Output is correct
8	Correct	349 ms	33892 KB	Output is correct
9	Correct	428 ms	33892 KB	Output is correct
10	Correct	318 ms	33892 KB	Output is correct
11	Correct	294 ms	33892 KB	Output is correct
12	Correct	281 ms	33892 KB	Output is correct
13	Correct	240 ms	33892 KB	Output is correct
14	Correct	264 ms	33892 KB	Output is correct
15	Correct	240 ms	33892 KB	Output is correct
16	Correct	208 ms	33892 KB	Output is correct
17	Correct	244 ms	33892 KB	Output is correct
18	Correct	202 ms	33892 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	24952 KB	Output is correct
2	Correct	32 ms	25196 KB	Output is correct
3	Correct	32 ms	25380 KB	Output is correct
4	Correct	40 ms	25424 KB	Output is correct
5	Correct	47 ms	25444 KB	Output is correct
6	Correct	34 ms	25540 KB	Output is correct
7	Correct	36 ms	25552 KB	Output is correct
8	Correct	42 ms	25644 KB	Output is correct
9	Correct	31 ms	25644 KB	Output is correct
10	Correct	29 ms	25644 KB	Output is correct
11	Correct	44 ms	25644 KB	Output is correct
12	Correct	30 ms	25644 KB	Output is correct
13	Correct	31 ms	25644 KB	Output is correct
14	Correct	44 ms	25644 KB	Output is correct
15	Correct	42 ms	25644 KB	Output is correct
16	Correct	45 ms	25644 KB	Output is correct
17	Correct	39 ms	25644 KB	Output is correct
18	Correct	36 ms	25644 KB	Output is correct
19	Correct	63 ms	26416 KB	Output is correct
20	Correct	73 ms	26668 KB	Output is correct
21	Correct	78 ms	26668 KB	Output is correct
22	Correct	74 ms	26796 KB	Output is correct
23	Correct	54 ms	26796 KB	Output is correct
24	Correct	66 ms	26796 KB	Output is correct
25	Correct	53 ms	26796 KB	Output is correct
26	Correct	52 ms	26796 KB	Output is correct
27	Correct	51 ms	26796 KB	Output is correct
28	Correct	67 ms	26796 KB	Output is correct
29	Correct	50 ms	27816 KB	Output is correct
30	Correct	185 ms	30884 KB	Output is correct
31	Correct	390 ms	33880 KB	Output is correct
32	Correct	419 ms	33892 KB	Output is correct
33	Correct	347 ms	33892 KB	Output is correct
34	Correct	349 ms	33892 KB	Output is correct
35	Correct	404 ms	33892 KB	Output is correct
36	Correct	349 ms	33892 KB	Output is correct
37	Correct	428 ms	33892 KB	Output is correct
38	Correct	318 ms	33892 KB	Output is correct
39	Correct	294 ms	33892 KB	Output is correct
40	Correct	281 ms	33892 KB	Output is correct
41	Correct	240 ms	33892 KB	Output is correct
42	Correct	264 ms	33892 KB	Output is correct
43	Correct	240 ms	33892 KB	Output is correct
44	Correct	208 ms	33892 KB	Output is correct
45	Correct	244 ms	33892 KB	Output is correct
46	Correct	202 ms	33892 KB	Output is correct
47	Correct	1267 ms	50908 KB	Output is correct
48	Correct	5327 ms	103928 KB	Output is correct
49	Correct	5789 ms	111420 KB	Output is correct
50	Correct	6096 ms	111636 KB	Output is correct
51	Correct	6710 ms	111664 KB	Output is correct
52	Correct	6243 ms	111696 KB	Output is correct
53	Correct	6477 ms	111696 KB	Output is correct
54	Correct	5596 ms	111696 KB	Output is correct
55	Correct	5842 ms	111696 KB	Output is correct
56	Correct	6062 ms	111696 KB	Output is correct
57	Correct	5809 ms	111696 KB	Output is correct
58	Correct	6246 ms	111696 KB	Output is correct
59	Correct	5185 ms	111696 KB	Output is correct
60	Correct	5003 ms	111696 KB	Output is correct
61	Correct	5103 ms	111696 KB	Output is correct
62	Correct	5106 ms	111696 KB	Output is correct
63	Correct	4315 ms	111696 KB	Output is correct
64	Correct	4364 ms	111696 KB	Output is correct
65	Correct	4583 ms	111696 KB	Output is correct
66	Correct	4105 ms	111696 KB	Output is correct
67	Correct	4178 ms	111696 KB	Output is correct

답안 #58374

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