제출 #1264239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264239		tvgk	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1654 ms	46228 KiB

bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 5e5 + 7;

int tree[mxN * 8], lazy[mxN * 8];
vector<ii> val;

void Down(int j)
{
    tree[j * 2] += lazy[j];
    lazy[j * 2] += lazy[j];
    tree[j * 2 + 1] += lazy[j];
    lazy[j * 2 + 1] += lazy[j];

    lazy[j] = 0;
}

void Upd(int u, int v, int inc, int j = 1, int l = 0, int r = val.size() - 1)
{
    if (u > r || l > v)
        return;

    if (u <= l && r <= v)
    {
        tree[j] += inc;
        lazy[j] += inc;
        return;
    }
    Down(j);

    int mid = (l + r) / 2;
    Upd(u, v, inc, j * 2, l, mid);
    Upd(u, v, inc, j * 2 + 1, mid + 1, r);
    tree[j] = max(tree[j * 2], tree[j * 2 + 1]);
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	for (int i = 0; i < A.size(); i++)
        val.push_back({A[i], i});
    for (int i = 0; i < X.size(); i++)
        val.push_back({V[i], X[i]});
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());

    for (int i = 0; i < A.size(); i++)
    {
        int j = lower_bound(val.begin(), val.end(), ii(A[i], i)) - val.begin();
        Upd(j, j, i);
        Upd(j + 1, val.size(), -1);
    }

    vector<int> answer(X.size());
    for (int i = 0; i < X.size(); i++)
    {
        int j = lower_bound(val.begin(), val.end(), ii(A[X[i]], X[i])) - val.begin();
        Upd(j, j, -X[i]);
        Upd(j + 1, val.size(), 1);

        A[X[i]] = V[i];
        j = lower_bound(val.begin(), val.end(), ii(A[X[i]], X[i])) - val.begin();
        Upd(j, j, X[i]);
        Upd(j + 1, val.size(), -1);

        answer[i] = tree[1];
    }
	return answer;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40