제출 #1027366

#제출 시각아이디문제언어결과실행 시간메모리
1027366boyliguanhanAliens (IOI16_aliens)C++17
100 / 100
662 ms48720 KiB
#include "aliens.h" #include<bits/stdc++.h> #pragma GCC optimize(2) #define sq(k) (k)*(k) typedef long long ll; using namespace std; ll VL[100100],rev[100100]; pair<ll,int>dp[100100]; struct seg{ ll k,b,cnt; inline pair<ll,int> operator()(int x){ return {k*x+b,cnt}; } seg(){k=0,b=1e18,cnt=0;} seg(ll k_,ll b_,ll cnt_){k=k_,b=b_,cnt=cnt_;} }; struct link_cut_tree{ seg T[1<<20]; int lc[1<<20]; int rc[1<<20]; int CC; int rt; void upd(int &i,int l,int r,seg SG){ if(!i)return void(T[i=++CC]=SG); if(l==r-1) { if(T[i](l)>SG(l)) swap(T[i],SG); return; } if(T[i].k>SG.k)swap(T[i],SG); if(T[i](l+r>>1)<SG(l+r>>1)) return upd(lc[i],l,l+r>>1,SG); swap(T[i],SG),upd(rc[i],l+r>>1,r,SG); } pair<ll,int> qry(int i,int l,int r,int p){ if(!i) return {(ll)1e18,0}; if(l==r-1)return T[i](p); if(l+r>>1<=p) return min(T[i](p),qry(rc[i],l+r>>1,r,p)); return min(T[i](p),qry(lc[i],l,l+r>>1,p)); } void reset(){ rt=0; for(int i=1;i<=CC;i++) lc[i]=rc[i]=0; CC=0; } inline void addline(ll cnt,ll k,ll b){ upd(rt,1,1e6+1,seg(k,b,cnt)); } inline pair<ll,int>querypos(int pos){ return qry(rt,1,1e6+1,pos); } link_cut_tree(){rt=CC=0;memset(lc,0,sizeof lc);memset(rc,0,sizeof rc);} } LCT; ll whttoad(int i){ if(rev[i]>=VL[i+1]) return sq(rev[i]-VL[i+1]+1); return 0; } int dodp(ll pen,int n){ LCT.reset(); LCT.addline(0,-2*VL[1]+2,sq(VL[1]-1)); for(int i=1;i<=n;i++) { dp[i]=LCT.querypos(rev[i]); dp[i].second++; dp[i].first+=pen+sq(rev[i]); LCT.addline(dp[i].second,-2*VL[i+1]+2,sq(VL[i+1]-1)+dp[i].first-whttoad(i)); } return dp[n].second; } ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) { ll MXX=m; swap(m,n); map<int,int>mp; int CC=0; map<int,int>mp2; for(int i=0;i<m;i++){ r[i]++;c[i]++; if(r[i]>c[i]) swap(r[i],c[i]); mp[c[i]]; if(mp2.count(c[i])) mp2[c[i]]=min(mp2[c[i]],r[i]); else mp2[c[i]]=r[i]; } vector<int>todie; int sfc=1e9; auto it=mp2.end(); do { it--; if(it->second>=sfc) todie.push_back(it->first); else sfc=it->second; }while(it!=mp2.begin()); for(auto i:todie) mp.erase(i),mp2.erase(i); for(auto&[i,j]:mp) rev[j=++CC]=i,VL[j]=mp2[i]; n=mp.size(); ll L=0,R=MXX*MXX,res=0; while(L<=R){ ll mid=L+R>>1; if(dodp(mid,n)<=k) R=mid-1,res=mid; else L=mid+1; } dodp(res,n); return dp[n].first-res*k; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In member function 'void link_cut_tree::upd(int&, int, int, seg)':
aliens.cpp:31:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         if(T[i](l+r>>1)<SG(l+r>>1))
      |                 ~^~
aliens.cpp:31:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         if(T[i](l+r>>1)<SG(l+r>>1))
      |                            ~^~
aliens.cpp:32:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |             return upd(lc[i],l,l+r>>1,SG);
      |                                ~^~
aliens.cpp:33:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         swap(T[i],SG),upd(rc[i],l+r>>1,r,SG);
      |                                 ~^~
aliens.cpp: In member function 'std::pair<long long int, int> link_cut_tree::qry(int, int, int, int)':
aliens.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         if(l+r>>1<=p)
      |            ~^~
aliens.cpp:39:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |             return min(T[i](p),qry(rc[i],l+r>>1,r,p));
      |                                          ~^~
aliens.cpp:40:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         return min(T[i](p),qry(lc[i],l,l+r>>1,p));
      |                                        ~^~
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:102:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |         ll mid=L+R>>1;
      |                ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...