oj.uz

Submission #392085

# Submission time Handle Problem Language Result Execution time Memory
392085 2021-04-20T12:41:16 Z muhammad_hokimiyon Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 242 ms 195428 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000500;

int G;
int a[maxn];
set<int> s[4 * maxn];
int f[4 * maxn];
int t[4 * maxn];
int lz[4 * maxn];

void push(int x)
{
    lz[x + x] += lz[x];
    lz[x + x + 1] += lz[x];
    t[x + x] += lz[x];
    t[x + x + 1] += lz[x];
    lz[x] = 0;
}

void upd(int x, int l, int r, int p, int val)
{
    if(l == r){
        t[x] -= f[x];
        if(val > 0)s[x].insert(val);
        else s[x].erase(val);
        if(s[x].empty())f[x] = 0;
        else f[x] = *--s[x].end();
        t[x] += f[x];
        return;
    }
    push(x);
    int m = (l + r) / 2;
    if(p <= m)upd(x + x, l, m, p, val);
    else upd(x + x + 1, m + 1, r, p, val);
    t[x] = max(t[x + x], t[x + x + 1]);
}

void upd(int x, int l, int r, int tl, int tr, int val)
{
    if(tl > tr)return;
    if(l == tl && r == tr){
        t[x] += val;
        lz[x] += val;
        return;
    }
    int m = (l + r) / 2;
    push(x);
    upd(x + x, l, m, tl, min(tr, m), val);
    upd(x + x + 1, m + 1, r, max(tl, m + 1), tr, val);
    t[x] = max(t[x + x], t[x + x + 1]);
}

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	int Q=X.size();
	vector<int> answer;
	int n = (int)A.size();
	vector<int> g;
	for(int i = 0; i < Q; i++){
        g.push_back(V[i]);
	}
	for(int i = 0; i < n; i++){
        g.push_back(A[i]);
	}
	map<int, int> m;
	sort(g.begin(), g.end());
    for(auto x : g){
        if(m.find(x) == m.end()){
            m[x] = ++G;
        }
    }
    for(int i = 0; i < n; i++){
        A[i] = m[A[i]];
        upd(1, 1, G, A[i], G, -1);
        upd(1, 1, G, A[i], i + 1);
	}
    for(int i = 0; i < Q; i++){
        V[i] = m[V[i]];
        upd(1, 1, G, A[X[i]], -(X[i] + 1));
        upd(1, 1, G, A[X[i]], G, 1);
        A[X[i]] = V[i];
        upd(1, 1, G, A[X[i]], (X[i] + 1));
        upd(1, 1, G, A[X[i]], G, -1);
        answer.push_back(t[1]);
    }
    return answer;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 189940 KB Output is correct
2 Correct 174 ms 192220 KB Output is correct
3 Incorrect 242 ms 195428 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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