oj.uz

Submission #248856

# Submission time Handle Problem Language Result Execution time Memory
248856 2020-07-13T14:49:05 Z egekabas Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 176 ms 99312 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){
        assert(a[x[i]] <= N);
        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 53 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 53 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 78 ms 96248 KB Output is correct
2 Correct 121 ms 97652 KB Output is correct
3 Correct 174 ms 99184 KB Output is correct
4 Correct 176 ms 99184 KB Output is correct
5 Correct 166 ms 99184 KB Output is correct
6 Correct 167 ms 99184 KB Output is correct
7 Correct 164 ms 99100 KB Output is correct
8 Correct 163 ms 99184 KB Output is correct
9 Correct 163 ms 99184 KB Output is correct
10 Correct 153 ms 99184 KB Output is correct
11 Correct 167 ms 99184 KB Output is correct
12 Correct 152 ms 99184 KB Output is correct
13 Correct 154 ms 99184 KB Output is correct
14 Correct 159 ms 99160 KB Output is correct
15 Correct 156 ms 99184 KB Output is correct
16 Correct 168 ms 99108 KB Output is correct
17 Correct 158 ms 99184 KB Output is correct
18 Correct 171 ms 99312 KB Output is correct

Subtask #4
0 / 40.0

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