Submission #1028771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028771		gs25	수족관 3 (KOI13_aqua3)	C++17	18 / 100	291 ms	26496 KiB

aqua3

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll; 

#define int ll 
const int MAXN = 300100; 

int seg[MAXN*4]; 
int x[MAXN], y[MAXN], child[MAXN], L[MAXN], R[MAXN], vis[MAXN]; 
priority_queue<pair<ll,int>> pq; 
ll fuck[MAXN]; 

void build_rmq(int node, int s, int e){
  if(s==e){
    seg[node] = s; return; 
  }
  int m = s+e>>1; 
  build_rmq(2*node, s,m); build_rmq(2*node+1,m+1,e); 
  int a = seg[2*node], b = seg[2*node+1]; 
  seg[node] = (y[a]>y[b]) ? b : a; 
}

int query(int node, int s, int e, int l, int r){
  if(r<s || l>e) return -1; 
  if(l<=s && e<=r) return seg[node]; 
  int m = s+e>>1; 
  int a = query(2*node,s,m,l,r), b = query(2*node+1,m+1,e,l,r); 
  if(a==-1) return b; if(b==-1) return a; 
  return y[a]>y[b] ? b : a; 
}
int n; 
int pv; 
void build(int node, int s, int e, int h){
  int idx = query(1,1,n,s,e); 
  //cerr << idx << endl; 
  ll val = (ll)(x[e]-x[s-1])*(y[idx]-h); 
  //cerr << x[s-1] << endl; 
  L[node] = -1, R[node] = -1; 
  if(s<=idx-1){
    pv++; 
    L[node] = pv; 
    build(pv,s,idx-1,y[idx]); 
  }
  if(idx+1<=e){
    pv++; 
    R[node] = pv; 
    build(pv,idx+1,e,y[idx]); 
  }
  ll l = (L[node]!=-1 ? fuck[L[node]] : 0), r = (R[node]!=-1 ? fuck[R[node]] : 0); 
  fuck[node] = val + max(l,r); 
  if(l>r) child[node] = L[node]; 
  else if(r>l) child[node] = R[node]; 
  else{
    if(r==0) child[node] = -1; 
    else child[node] = L[node]; 
  }
  pq.push({fuck[node],node}); 
}

int32_t main(void){
  ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 
  cin >> n; n = (n-1)>>1; 
  cin >> x[0] >> y[0]; 
  for(int i=1; i<=n; i++){
    cin >> x[i] >> y[i]; cin >> x[i] >> y[i]; 
  }
  cin >> x[0] >> y[0]; 
  x[0] = 0, y[0] = 0; 
  build_rmq(1,1,n); 
  
  build(0,1,n,0); //cerr << "fuck" << endl; 
  int k; cin >> k; 
  ll ans = 0; int cnt = 0; 
  while(cnt<k && !pq.empty()){
    auto [val, i] = pq.top(); pq.pop(); 
    //cerr << val << " " << i << endl; 
    if(vis[i]) continue; ans += val; 
    //cerr << i << " " << val << endl;
    while(i!=-1) {
      vis[i] = 1; i = child[i]; 
    }
    cnt++; 
  }
  cout << ans; 
}

Compilation message (stderr)

aqua3.cpp: In function 'void build_rmq(ll, ll, ll)':
aqua3.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |   int m = s+e>>1;
      |           ~^~
aqua3.cpp: In function 'll query(ll, ll, ll, ll, ll)':
aqua3.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |   int m = s+e>>1;
      |           ~^~
aqua3.cpp:30:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   30 |   if(a==-1) return b; if(b==-1) return a;
      |   ^~
aqua3.cpp:30:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   30 |   if(a==-1) return b; if(b==-1) return a;
      |                       ^~
aqua3.cpp: In function 'int32_t main()':
aqua3.cpp:79:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   79 |     if(vis[i]) continue; ans += val;
      |     ^~
aqua3.cpp:79:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   79 |     if(vis[i]) continue; ans += val;
      |                          ^~~

• Subtask 1: 18 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 21
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16