Submission #951384

#	Time	Username	Problem	Language	Result	Execution time	Memory
951384		Vladth11	Measures (CEOI22_measures)	C++14	0 / 100	1554 ms	12864 KiB

Main

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const ll NMAX = 200001;
const ll INF = (1LL << 58);
const ll nrbits = 20;
const ll MOD = 998244353;
const int VMAX = 10;

int a[NMAX];
int b[NMAX];
unordered_map <int, int> mp;

multiset <int> mst;
int lft[NMAX];
int rgt[NMAX];
int cnt;
int d;

void addRight(int x, int val) {
    for(; x > 0; x -= x&(-x))
        rgt[x] += val;
}

void addLeft(int x, int val) {
    for(; x <= cnt; x += x&(-x))
        lft[x] += val;
}

int toRight(int x) {
    int val = 0;
    for(; x <= cnt; x += x&(-x))
        val += rgt[x];
    return val;
}

int toLeft(int x) {
    int val = 0;
    for(; x > 0; x -= x&(-x))
        val += lft[x];
    return val;
}

void baga(int x) {
    auto dupa = mst.lower_bound(x);
    if(dupa == mst.begin() && dupa != mst.end()) {
        int dr = (*dupa);
        int dist = (dr - x);
        if(dist < d) {
            addLeft(mp[dr], d - dist);
            addRight(mp[x], d - dist);
        }
    } else if(dupa != mst.end()) {
        auto inainte = prev(dupa);
        int st = (*inainte);
        int dr = (*dupa);
        int dist = dr - st;
        if(dist < d) {
            addLeft(mp[dr], -(d - dist));
            addRight(mp[st], -(d - dist));
        }
        dist = dr - x;
        if(dist < d) {
            addLeft(mp[dr], d - dist);
            addRight(mp[x], d - dist);
        }
        dist = x - st;
        if(dist < d) {
            addLeft(mp[x], d - dist);
            addRight(mp[st], d - dist);
        }
    } else {
        if(mst.size()) {
            auto inainte = prev(dupa);
            int st = (*inainte);
            int dist = (x - st);
            if(dist < d) {
                addLeft(mp[x], d - dist);
                addRight(mp[st], d - dist);
            }
        }
    }
    mst.insert(x);
}

int f(int x) {
    int dr = 0;
    int st = 0;
    auto dupa = mst.lower_bound(x);
    if(dupa == mst.end()) {
        return toLeft(mp[(*prev(dupa))]);
    } else {
        dr = toRight(mp[(*dupa)]);
    }
    if(dupa == mst.begin()) {
        return toRight(mp[(*dupa)]);
    } else {
        st = toLeft(mp[(*prev(dupa))]);
    }
    int dif = (*dupa) - (*prev(dupa)), adaos = 0;
    int difini = dif;
    if(dif < d) {
        dif = d - dif;
        adaos = dr - st + dif;
    }
    adaos = max(adaos, 0);
    adaos = min(adaos, 2 * dif);
    return max(2 * st + adaos, 2 * dr + 2 * dif - adaos);
}

int ternary(int a, int b) {
    if(a == b) {
        return f(a);
    }
    if(a + 1 == b) {
        return min(f(a), f(b));
    }
    int mid1 = a + (b - a) / 3;
    int mid2 = b - (b - a) / 3;
    if(f(mid1) < f(mid2)) {
        return ternary(a, mid2 - 1);
    }
    return ternary(mid1 +  1, b);
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i, m, x;
    cin >> n >> m >> d;
    vector <int> nrm;
    for(i = 1; i <= n; i++) {
        cin >> a[i];
        nrm.push_back(a[i]);
    }
    for(i = 1; i <= m; i++) {
        cin >> b[i];
        nrm.push_back(b[i]);
    }
    sort(nrm.begin(), nrm.end()); /// ESTI RETARD?
    int last = -1;
    for(auto x : nrm) {
        if(x != last) {
            cnt++;
        }
        mp[x] = cnt;
        last = x;
    }
    for(i = 1; i <= n; i++) {
        baga(a[i]);
    }
    for(i = 1; i <= m; i++) {
        baga(b[i]);
        int sol = 2e9;
        for(auto j : mst){
            sol = min(sol, f(j));
            sol = min(sol, f(j - 1));
            sol = min(sol, f(j + 1));
        }
        cout << sol/2;
        if(sol%2) {
            cout << ".5";
        }
        cout << " ";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int f(int)':
Main.cpp:108:9: warning: unused variable 'difini' [-Wunused-variable]
  108 |     int difini = dif;
      |         ^~~~~~
Main.cpp: In function 'int main()':
Main.cpp:141:18: warning: unused variable 'x' [-Wunused-variable]
  141 |     int n, i, m, x;
      |                  ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41