oj.uz

Submission #248855

# Submission time Handle Problem Language Result Execution time Memory
248855 2020-07-13T14:48:26 Z egekabas Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 186 ms 99184 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];
        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 55 ms 94584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 94584 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 86 ms 96248 KB Output is correct
2 Correct 125 ms 97652 KB Output is correct
3 Correct 186 ms 99184 KB Output is correct
4 Correct 182 ms 99184 KB Output is correct
5 Correct 169 ms 99184 KB Output is correct
6 Correct 176 ms 99184 KB Output is correct
7 Correct 169 ms 99184 KB Output is correct
8 Correct 167 ms 99184 KB Output is correct
9 Correct 165 ms 99184 KB Output is correct
10 Correct 163 ms 99184 KB Output is correct
11 Correct 167 ms 99184 KB Output is correct
12 Correct 167 ms 99184 KB Output is correct
13 Correct 160 ms 99184 KB Output is correct
14 Correct 157 ms 99184 KB Output is correct
15 Correct 161 ms 99184 KB Output is correct
16 Correct 153 ms 99184 KB Output is correct
17 Correct 155 ms 99184 KB Output is correct
18 Correct 161 ms 99184 KB Output is correct

Subtask #4
0 / 40.0

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