oj.uz

Submission #1048844

# Submission time Handle Problem Language Result Execution time Memory
1048844 2024-08-08T09:48:16 Z RecursiveCo Bikeparking (EGOI24_bikeparking) C++17
9 / 100
 238 ms 25444 KB 
// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

//#define int long long int

template <typename T, typename I>
struct segtree {
    int n;
    vector<T> tree;
    vector<I> initial;
    T id;

    segtree(int i_n, vector<I> i_initial, T i_id): n(i_n), initial(i_initial), id(i_id) {
        tree.resize(4 * n);
    }

    T conquer(T left, T right) {
        // write your conquer function
    }

    T value(I inp) {
        // write your value function
    }

    void build(int v, int l, int r) {
        if (l == r) tree[v] = value(initial[l]);
        else {
            int middle = (l + r) / 2;
            build(2 * v, l, middle);
            build(2 * v + 1, middle + 1, r);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    void upd(int v, int l, int r, int i, I x) {
        if (l == r) tree[v] = value(x);
        else {
            int middle = (l + r) / 2;
            if (middle >= i) upd(2 * v, l, middle, i, x);
            else upd(2 * v + 1, middle + 1, r, i, x);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    T query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        else if (r < ql || qr < l) return id;
        int middle = (l + r) / 2;
        T left = query(2 * v, l, middle, ql, qr);
        T right = query(2 * v + 1, middle + 1, r, ql, qr);
        return conquer(left, right);
    }
};

// vector<int>

vector<int> X;
vector<int> Y;

int evalfast(int middle) {
    int n = X.size(); // = Y.size()
    int bad = 0;
    int neutral = 0;
    int suf = 0;
    int ptr;
    int only;
    for (int i = n - 1; i >= 0; i--) {
        if (suf + Y[i] >= middle + 1) {
            ptr = i;
            only = middle + 1 - suf;
        }
        suf += Y[i];
    }
    int xpref = 0;
    int ypref = 0;
    bool active = true;
    forto(n, i) {
        if (xpref >= middle + 1) break;
        if (ypref <= xpref) {
            while (ptr < n) {
                int here = (active? only: Y[ptr]);
                active = false;
                if (ypref + here > xpref) {
                    ypref += here;
                    if (i > ptr) bad++;
                    else if (i == ptr) neutral++;
                    ptr++;
                    break;
                }
                ypref += here;
                ptr++;
            }
        } else {
            if (i > ptr) bad++;
            else if (i == ptr) neutral++;
        }
        xpref += X[i];
    }
    if (bad) return -1;
    return neutral;
}

pair<int, int> evalslow(int middle) {
    vector<array<int, 3>> events;
    int pref = 0;
    int n = X.size(); // = Y.size()
    forto(n, i) {
        if (pref >= middle + 1) break;
        events.push_back({pref, 0, i});
        pref += X[i];
    }
    int suf = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (suf >= middle + 1) break;
        suf += Y[i];
        events.push_back({max(0, middle + 1 - suf), 1, i});
    }
    sortl(events);
    int bad = 0;
    int nvals = 0;
    int neutral = 0;
    int x = 0;
    int y = 0;
    int ptr = 0;
    int s = events.size();
    int val = 0;
    while (ptr < s) {
        while (ptr < s && events[ptr][0] == val) {
            int typ = events[ptr][1];
            int setto = events[ptr][2];
            if (typ) y = setto;
            else x = setto;
            ptr++;
        }
        if (y < x) bad++;
        else if (y == x) nvals++, neutral += (ptr < s? events[ptr][0]: middle + 1) - val;
        if (ptr < s) val = events[ptr][0];
    }
    if (bad) return {-1, -1};
    return {nvals, neutral};
}

signed main() {
    improvePerformance;
    get(n);
    forto(n, i) {
        get(x);
        X.push_back(x);
    }
    forto(n, i) {
        get(y);
        Y.push_back(y);
    }
    int ysum = 0;
    forto(n, i) ysum += Y[i];
    if (ysum == 0) {
        out(0);
        return 0;
    }
    int xsum = 0;
    forto(n, i) {
        if (xsum + X[i] >= ysum) {
            X[i] = ysum - xsum;
            break;
        }
        xsum += X[i];
    }
    int l = 0;
    int r = ysum;
    while (r - l > 1) {
        int middle = (l + r) / 2;
        int value = evalfast(middle);
        if (value == -1 || value > 2) r = middle;
        else l = middle;
    }
    if (evalslow(l).second == -1) out(-ysum);
    else out((l + 1) - (ysum - (l + 1)) - evalslow(l).second);
}

Compilation message

Main.cpp: In function 'int evalfast(int)':
Main.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
Main.cpp:91:5: note: in expansion of macro 'forto'
   91 |     forto(n, i) {
      |     ^~~~~
Main.cpp: In function 'std::pair<int, int> evalslow(int)':
Main.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
Main.cpp:121:5: note: in expansion of macro 'forto'
  121 |     forto(n, i) {
      |     ^~~~~
Main.cpp: In function 'int main()':
Main.cpp:10:23: warning: unnecessary parentheses in declaration of 'n' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
Main.cpp:159:5: note: in expansion of macro 'get'
  159 |     get(n);
      |     ^~~
Main.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
Main.cpp:160:5: note: in expansion of macro 'forto'
  160 |     forto(n, i) {
      |     ^~~~~
Main.cpp:10:23: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
Main.cpp:161:9: note: in expansion of macro 'get'
  161 |         get(x);
      |         ^~~
Main.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
Main.cpp:164:5: note: in expansion of macro 'forto'
  164 |     forto(n, i) {
      |     ^~~~~
Main.cpp:10:23: warning: unnecessary parentheses in declaration of 'y' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
Main.cpp:165:9: note: in expansion of macro 'get'
  165 |         get(y);
      |         ^~~
Main.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
Main.cpp:169:5: note: in expansion of macro 'forto'
  169 |     forto(n, i) ysum += Y[i];
      |     ^~~~~
Main.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
Main.cpp:175:5: note: in expansion of macro 'forto'
  175 |     forto(n, i) {
      |     ^~~~~
Main.cpp: In function 'int evalfast(int)':
Main.cpp:97:27: warning: 'only' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |                 if (ypref + here > xpref) {
      |                     ~~~~~~^~~~~~
Main.cpp:109:18: warning: 'ptr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |             else if (i == ptr) neutral++;
      |                  ^~

Subtask #1
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 17 ms 5588 KB Output is correct
6 Correct 174 ms 23812 KB Output is correct
7 Correct 208 ms 22484 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 18 ms 4516 KB Output is correct
3 Correct 184 ms 23908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 218 ms 23652 KB Output is correct
11 Correct 238 ms 25444 KB Output is correct
12 Correct 217 ms 22416 KB Output is correct
13 Correct 221 ms 23360 KB Output is correct
14 Correct 205 ms 25356 KB Output is correct
15 Correct 185 ms 23528 KB Output is correct
16 Incorrect 134 ms 18492 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -