제출 #1173806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1173806		Zero_OP	나일강 (IOI24_nile)	C++20	38 / 100	61 ms	21268 KiB

nile

#include <bits/stdc++.h>

#ifndef LOCAL
      #include "nile.h"
#endif // LOCAL

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ull = unsigned long long;
using ld = long double;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vc = vector<char>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

using vvi = vector<vi>;
using vvl = vector<vl>;

const int MAX = 1e5 + 5;

int N, W[MAX], A[MAX], B[MAX], rmq[20][MAX];

void processRMQ(){
      FOR(i, 0, N) rmq[0][i] = A[i] - B[i];
      for(int i = 1; (1 << i) <= N; ++i){
            for(int j = 0; j + (1 << i) <= N; ++j){
                  rmq[i][j] = min(rmq[i-1][j], rmq[i-1][j + (1 << (i-1))]);
            }
      }
}

int query_rmq(int l, int r){
      int k = 31 - __builtin_clz(r - l + 1);
      return min(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}

int min_except(int l, int r){
      int res = min(A[l] - B[l], A[r] - B[r]);
      if(l+2 <= r-2) minimize(res, query_rmq(l+2, r-2));
      return res;
}

namespace DSU{
      int lab[MAX], l[MAX], r[MAX];
      ll sumB[MAX], result;
      multiset<pi> values[MAX];

      void init(int N){
            FOR(i, 0, N) {
                  lab[i] = -1;
                  l[i] = r[i] = i;
                  sumB[i] = B[i];
                  result += A[i];
            }
      }

      ll calc(int u, int limit){
            ///imagine we have x x x x ... x x x can be paired consecutively
            ///if sz(x) is even -> answer = sum B[i]
            ///if sz(x) is odd --> answer = sum B[i] - min(A[i] - B[i])
            ///- special case 1 : W[l] cannot connect to W[l+2] -> A[l] - B[l] + A[l+1] - B[l+1]
            ///- special case 2 : W[r] cannot connect to W[r-2] -> A[r] - B[r] + A[r-1] - B[r-1]
//            cout << dbg(l[u]) << dbg(r[u]) << dbg(limit);
            if((-lab[u]) & 1 ^ 1) return sumB[u];
            if((-lab[u]) == 1) return A[u];
            ll cur = sumB[u] + min_except(l[u], r[u]);
            if(W[l[u]+2] - W[l[u]] <= limit) minimize(cur, sumB[u] + A[l[u]+1] - B[l[u]+1]);
            if(W[r[u]] - W[r[u]-2] <= limit) minimize(cur, sumB[u] + A[r[u]-1] - B[r[u]-1]);
//            cout << dbg(cur) << '\n';
            return cur;
      }

      int root(int u){
            return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
      }

      bool join(int u, int v, int limit){
            u = root(u); v = root(v);
            if(u == v) return false;
            if(lab[u] > lab[v]) swap(u, v);

            result -= calc(u, limit);
            result -= calc(v, limit);

            sumB[u] += sumB[v];
            lab[u] += lab[v];
            lab[v] = u;

            minimize(l[u], l[v]);
            maximize(r[u], r[v]);
            result += calc(u, limit);

//            cout << dbg(l[u]) << dbg(r[u]) << dbg(calc(u, limit)) << '\n';

            return true;
      }

      void retake(int u, int old_limit, int new_limit){
            result -= calc(u, old_limit);
            result -= calc(u, new_limit);
      }
}

vl calculate_costs(vi _W, vi _A, vi _B, vi E){
      N = sz(_W);
      int Q = sz(E);

      vpi queries(Q);
      FOR(i, 0, Q) queries[i] = mp(E[i], i);
      sort(all(queries));

      vector<tuple<int, int, int>> ord;
      FOR(i, 0, N) ord.pb(mt(_W[i], _A[i], _B[i]));
      sort(all(ord));
      FOR(i, 0, N) tie(W[i], A[i], B[i]) = ord[i];

      DSU::init(N);

      vector<pi> edges;
      FOR(i, 1, N){
            edges.eb(W[i] - W[i-1], i);
      }

      sort(all(edges));

      processRMQ();

      vl ans(Q);
      int j = 0;
      FOR(i, 0, Q){
            while(j < sz(edges) && edges[j].ff <= queries[i].ff){
                  DSU::join(edges[j].ss-1, edges[j].ss, queries[i].ff);
                  ++j;
            }
            ans[queries[i].ss] = DSU::result;
      }

      return ans;
}

#ifdef LOCAL

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

int main(){
      setIO();

      int N;
      cin >> N;
      vi W(N), A(N), B(N);
      FOR(i, 0, N) cin >> W[i] >> A[i] >> B[i];

      int Q;
      cin >> Q;
      vi E(Q);
      FOR(i, 0, Q) cin >> E[i];

      vl costs = calculate_costs(W, A, B, E);
      FOR(i, 0, sz(costs)){
            cout << costs[i] << '\n';
      }

      return 0;
}
#endif //LOCAL

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18