oj.uz

Submission #248857

# Submission time Handle Problem Language Result Execution time Memory
248857 2020-07-13T14:49:25 Z egekabas Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 179 ms 99252 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]);
    }
}
map<int, int> mpp;

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();
    vector<int> tmp;
    for(auto u : a)
        tmp.pb(u);
    for(auto u : v)
        tmp.pb(u);
    sort(tmp.begin(), tmp.end());
    tmp.resize(unique(tmp.begin(), tmp.end())-tmp.begin());
    N = 1000000;
    for(int i = 0; i < tmp.size(); ++i)
        mpp[tmp[i]] = i;
    for(int i = 0; i < n; ++i){
        a[i] = mpp[a[i]];
    }
    for(int i = 0; i < int(v.size()); ++i)
        v[i] = mpp[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];
                assert(a[x[i]] <= N);

        add(x[i]);
        ans[i] = max(seg[1], 0);
    }
    return ans;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < tmp.size(); ++i)
                    ~~^~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 94456 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 94456 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 77 ms 96248 KB Output is correct
2 Correct 120 ms 97652 KB Output is correct
3 Correct 175 ms 99184 KB Output is correct
4 Correct 164 ms 99184 KB Output is correct
5 Correct 166 ms 99184 KB Output is correct
6 Correct 169 ms 99184 KB Output is correct
7 Correct 171 ms 99184 KB Output is correct
8 Correct 176 ms 99180 KB Output is correct
9 Correct 179 ms 99172 KB Output is correct
10 Correct 166 ms 99184 KB Output is correct
11 Correct 154 ms 99184 KB Output is correct
12 Correct 154 ms 99184 KB Output is correct
13 Correct 158 ms 99184 KB Output is correct
14 Correct 160 ms 99184 KB Output is correct
15 Correct 159 ms 99252 KB Output is correct
16 Correct 164 ms 99184 KB Output is correct
17 Correct 158 ms 99184 KB Output is correct
18 Correct 158 ms 99184 KB Output is correct

Subtask #4
0 / 40.0

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