제출 #362777

#제출 시각아이디문제언어결과실행 시간메모리
362777DymoCake 3 (JOI19_cake3)C++14
0 / 100
1 ms384 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back #define endl "\n" const ll maxn =2e5+10; const ll mod=1e9+7; const ll base=1e18; ll st[4*maxn]; ll st1[4*maxn]; ll val[maxn]; ll pos[maxn]; pll a[maxn]; struct tk { ll n; ll l=1; ll r=0; void update(ll id,ll left,ll right,ll x,ll diff) { if (x>right||x<left) return ; if (left==right) { st[id]+=diff; st1[id]+=val[left]*diff; return ; } ll mid=(left+right)/2; update(id*2,left,mid, x, diff); update(id*2+1,mid+1, right, x, diff); st[id]=st[id*2]+st[id*2+1]; st1[id]=st1[id*2]+st1[id*2+1]; } void finit(ll n1) { l=1; r=0; init(1,1,n1); n=n1; } void init(ll id,ll left,ll right) { st[id]=0; st1[id]=0; if (left==right) return ; ll mid=(left+right)/2; init(id*2,left,mid); init(id*2+1,mid+1, right); } void ers(ll t) { update(1,1,n,t,-1); } void add(ll t) { update(1,1,n,t,1); } ll get1(ll lf,ll rt,ll x) { if (x<0) return -base; while (l>lf) { l--; add(pos[l]); } while (l<lf) { ers(pos[l]); l++; } while (r<rt) { r++; add(pos[r]); } while (r>rt) { ers(pos[r]); r--; } if (x>st[1]) { return st1[1]; } return get(1,1,n,x); } ll get(ll id,ll left,ll right,ll x) { if (left==right) { return val[left]*x; } ll mid=(left+right)/2; if (st[id*2+1]<x) { return get(id*2,left,mid,x-st[id*2+1])+st1[id*2+1]; } else { return get(id*2+1,mid+1,right,x); } } } man; ll ans[maxn]; void dac(ll l,ll r,ll low,ll high,ll d) { if (l>r) return ; ll mid=(l+r)/2; ll pos_best=-1; ans[mid]=-base; for (int i=low;i<=min(mid,min(mid-d+1,high));i++) { ll t=man.get1(i,mid,d)-2*(a[mid].ff-a[i].ff); if (ans[mid]<t) { ans[mid]=t; pos_best=i; } } dac(l,mid-1,low,pos_best,d); dac(mid+1,r,pos_best,high,d); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("t.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ll n,m; cin>> n>> m; vector<ll> vt; for (int i=1;i<=n;i++) { cin>>a[i].ss>>a[i].ff; vt.pb(a[i].ss); } sort(a+1,a+n+1); sort(vt.begin(),vt.end()); vt.resize(unique(vt.begin(),vt.end())-vt.begin()); for (int i=1;i<=n;i++) { pos[i]=lower_bound(vt.begin(),vt.end(),a[i].ss)-vt.begin()+1; } ll siz=vt.size(); for (int i=1;i<=siz;i++) { val[i]=vt[i-1]; } man.finit(siz); dac(m,n,1,n,m); ll res=0; for (int i=1;i<=n;i++) { res=max(res,ans[i]); } cout <<res; }

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

cake3.cpp: In function 'int main()':
cake3.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  143 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  144 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...