oj.uz

답안 #951383

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
951383 2024-03-21T20:18:06 Z Vladth11 Measures (CEOI22_measures) C++14
0 / 100
 1500 ms 22624 KB 
#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));
    int adaos = 0, difini = dif;
    if(dif < d){
        dif = d - dif;
        adaos = dr - st + dif;
    }
    adaos = max(adaos, 0);
    adaos = min(adaos, 2 * difini);
    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]);
    }
    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 = ternary((*mst.begin()) - 1, (*prev(mst.end())) + 1);
        cout << sol/2;
        if(sol%2){
            cout << ".5";
        }
        cout << " ";
    }
    return 0;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1550 ms 22624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1550 ms 22624 KB Time limit exceeded
2 Halted 0 ms 0 KB -