oj.uz

Submission #248853

# Submission time Handle Problem Language Result Execution time Memory
248853 2020-07-13T14:45:20 Z egekabas Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 155 ms 99104 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int seg[8000009];
int lazy[8000009];
void push(int v){
    lazy[2*v] += lazy[v];
    lazy[2*v+1] += lazy[v];
    seg[2*v] += lazy[v];
    seg[2*v+1] += lazy[v];
    lazy[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int val){
    if(r < tl || tr < l) return;
    if(l <= tl && tr <= r){
        seg[v] += val;
        lazy[v] += val;
    }
    else{
        push(v);
        upd(2*v, tl, (tl+tr)/2, l, r, val);
        upd(2*v+1, (tl+tr)/2+1, tr, l, r, val);
        seg[v] = max(seg[2*v], seg[2*v+1]);
    }
}
vector<int> mpp;
int get(int x){
    return lower_bound(mpp.begin(), mpp.end(), x)-mpp.begin();
}
set<int, greater<int>> s[2000009];
int n, N;
vector<int> a, x, v;

void erase(int idx){
    if(*s[a[idx]].begin() == idx+1){
        upd(1, 0, N, a[idx], a[idx], -(idx+1));
        s[a[idx]].erase(idx+1);
        if(s[a[idx]].size())
            upd(1, 0, N, a[idx], a[idx], *s[a[idx]].begin());
    }
    else
        s[a[idx]].erase(idx+1);
    upd(1, 0, N, a[idx], N, 1);
}
void add(int idx){
    if(s[a[idx]].empty()){
        upd(1, 0, N, a[idx], a[idx], (idx+1));        
    }
    else if(idx+1 > *s[a[idx]].begin()){
        upd(1, 0, N, a[idx], a[idx], -*s[a[idx]].begin());
        upd(1, 0, N, a[idx], a[idx], (idx+1));    
    }
    s[a[idx]].insert(idx+1);
    upd(1, 0, N, a[idx], N, -1);
}
vector<int> countScans(vector<int> a1, vector<int> a2, vector<int> a3){
    a = a1;
    x = a2;
    v = a3;
    n = a.size();
    for(auto u : a)
        mpp.pb(u);
    for(auto u : v)
        mpp.pb(u);
    sort(mpp.begin(), mpp.end());
    mpp.resize(unique(mpp.begin(), mpp.end())-mpp.begin());
    N = mpp.size()-1;

    for(int i = 0; i < n; ++i){
        a[i] = get(a[i]);
    }
    for(int i = 0; i < int(v.size()); ++i)
        v[i] = get(v[i]);

    
    for(int i = 0; i < n; ++i){
        s[a[i]].insert(i+1);
        upd(1, 0, N, a[i], n, -1);
    }
    for(int i = 0; i < n; ++i)
        if(*s[a[i]].begin() == i+1){
            upd(1, 0, N, a[i], a[i], i+1);
        }
    vector<int> ans(x.size());
    for(int i = 0; i < int(x.size()); ++i){
        erase(x[i]);
        a[x[i]] = v[i];
        add(x[i]);
        ans[i] = max(seg[1], 0);
    }
    return ans;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 94328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 94328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 96120 KB Output is correct
2 Correct 103 ms 97524 KB Output is correct
3 Correct 155 ms 98920 KB Output is correct
4 Correct 140 ms 98928 KB Output is correct
5 Correct 134 ms 98928 KB Output is correct
6 Correct 140 ms 99056 KB Output is correct
7 Correct 134 ms 98928 KB Output is correct
8 Correct 133 ms 98928 KB Output is correct
9 Correct 136 ms 98932 KB Output is correct
10 Correct 123 ms 99056 KB Output is correct
11 Correct 121 ms 98932 KB Output is correct
12 Correct 122 ms 98928 KB Output is correct
13 Correct 119 ms 98928 KB Output is correct
14 Correct 129 ms 98976 KB Output is correct
15 Correct 127 ms 99104 KB Output is correct
16 Correct 122 ms 98928 KB Output is correct
17 Correct 115 ms 98928 KB Output is correct
18 Correct 116 ms 99056 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 94328 KB Output isn't correct
2 Halted 0 ms 0 KB -