Submission #1173933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173933		Zero_OP	나일강 (IOI24_nile)	C++20	100 / 100	87 ms	30920 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;
const int inf = 1e9 + 9;

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

int rmq[2][20][MAX];

struct SegmentTree{
      vi st;
      int n;
      SegmentTree(int n) : n(n), st(n << 2, inf) {}

      void update(int id, int val){
            st[id+=n] = val;
            for(; id > 1; id >>= 1){
                  st[id>>1] = min(st[id], st[id^1]);
            }
      }

      int query(int l, int r){
            int result = inf;
            l += n; r += n + 1;
            for(; l < r; l >>= 1, r >>= 1){
                  if(l&1) minimize(result, st[l++]);
                  if(r&1) minimize(result, st[--r]);
            }
            return result;
      }
} Todd(0), Teven(0);

void processRMQ(){
      memset(rmq, 0x3, sizeof(rmq));
      FOR(i, 0, N) rmq[i&1][0][i] = A[i] - B[i], rmq[i&1^1][0][i] = inf;

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

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

namespace DSU{
      int lab[MAX], l[MAX], r[MAX];
      ll sumB[MAX], f[MAX], result;

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

      ll sum_range(int l, int r){
            return sumB[r] - (l > 0 ? sumB[l-1] : 0);
      }

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

      ll calc(int u){
            if((r[u] - l[u] + 1) & 1 ^ 1) return sum_range(l[u], r[u]);
            if(l[u] == r[u]) return A[u];
            int sub = query(l[u] & 1, l[u], r[u]);
            if(l[u]&1) minimize(sub, Teven.query(l[u]+1, r[u]-1));
            else minimize(sub, Todd.query(l[u]+1, r[u]-1));
            return sum_range(l[u], r[u]) + sub;
      }

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

            result -= f[u];
            result -= f[v];

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

            minimize(l[u], l[v]);
            maximize(r[u], r[v]);

            result += (f[u] = calc(u));
            return true;
      }

      void retake(int u){
            result -= f[u];
            result += (f[u] = calc(u));
      }
}

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];

      Todd = SegmentTree(N);
      Teven = SegmentTree(N);

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

      sort(all(adj));
      sort(all(adj2));

      DSU::init(N);
      processRMQ();

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

            vi applied;
            while(j2 < sz(adj2) && adj2[j2].ff <= queries[i].ff){
                  int pos = adj2[j2].ss;
                  assert(DSU::root(pos-1) == DSU::root(pos+1));
                  if(pos&1) Todd.update(pos, A[pos] - B[pos]);
                  else Teven.update(pos, A[pos] - B[pos]);
                  applied.pb(DSU::root(pos));
                  ++j2;
            }

            sort(all(applied)); compact(applied);
            for(auto u : applied){
                  DSU::retake(u);
            }

            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: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18