結果
問題 | No.1874 Minimum of Sum of Rectangles |
ユーザー |
|
提出日時 | 2022-03-11 22:45:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,480 bytes |
コンパイル時間 | 2,228 ms |
コンパイル使用メモリ | 209,272 KB |
最終ジャッジ日時 | 2025-01-28 08:56:59 |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | TLE * 3 |
other | TLE * 39 |
コンパイルメッセージ
main.cpp: In member function ‘ll segtree::update(ll, ll)’: main.cpp:93:5: warning: no return statement in function returning non-void [-Wreturn-type] 93 | } | ^
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for(long long i=0;i<(long long)(n);i++)#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)#define pb emplace_back#define lb(v,k) (lower_bound(all(v),(k))-v.begin())#define ub(v,k) (upper_bound(all(v),(k))-v.begin())#define fi first#define se second#define pi M_PI#define PQ(T) priority_queue<T>#define SPQ(T) priority_queue<T,vector<T>,greater<T>>#define dame(a) {out(a);return 0;}#define decimal cout<<fixed<<setprecision(15);#define all(a) a.begin(),a.end()#define rsort(a) {sort(all(a));reverse(all(a));}#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}#define popcnt __builtin_popcountlltypedef long long ll;typedef pair<ll,ll> P;typedef tuple<ll,ll,ll> PP;typedef tuple<ll,ll,ll,ll> PPP;using vi=vector<ll>;using vvi=vector<vi>;using vvvi=vector<vvi>;using vvvvi=vector<vvvi>;using vp=vector<P>;using vvp=vector<vp>;using vb=vector<bool>;using vvb=vector<vb>;const ll inf=1001001001001001001;const ll INF=1001001001;const ll mod=1000000007;const double eps=1e-10;template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}template<class T> void out(T a){cout<<a<<'\n';}template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}template<class T> void yesno(T b){if(b)out("yes");else out("no");}template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}class segtree{vi seg,co,lazy;ll N=1;void eval(ll k,ll l,ll r){seg[k]+=lazy[k]*co[k];if(r-l>1)rep(t,2)lazy[k*2+t]+=lazy[k];lazy[k]=0;}public:segtree(vi v,vi u){while(N<v.size())N*=2;seg=vi(N*2);co=vi(N*2);lazy=vi(N*2);rep(i,v.size())seg[i+N]=v[i];rep(i,v.size())co[i+N]=u[i];for(int i=N-1;i>0;i--)seg[i]=seg[i*2]+seg[i*2+1];for(int i=N-1;i>0;i--)co[i]=co[i*2]+co[i*2+1];}void add(ll x,ll a,ll b,ll k=1,ll l=0,ll r=-1){if(r==-1)r=N;eval(k,l,r);if(r<=a||b<=l)return;if(a<=l&&r<=b){lazy[k]+=x;eval(k,l,r);return;}add(x,a,b,k*2,l,(l+r)/2);add(x,a,b,k*2+1,(l+r)/2,r);seg[k]=seg[k*2]+seg[k*2+1];}ll get(ll a,ll b,ll k=1,ll l=0,ll r=-1){if(r==-1)r=N;eval(k,l,r);if(r<=a||b<=l)return 0;if(a<=l&&r<=b)return seg[k];return get(a,b,k*2,l,(l+r)/2)+get(a,b,k*2+1,(l+r)/2,r);}ll update(ll k,ll x){add(0,k,k+1);k+=N;co[k]=x;for(k>>=1;k>0;k>>=1)co[k]=co[k*2]+co[k*2+1];}};int main(){ll n;cin>>n;vp v(n);rep(i,n)cin>>v[i].fi>>v[i].se;sort(all(v));vi id(n);rep(i,n)id[i]=i;auto comp=[&](ll a,ll b){if(v[a].se==v[b].se)return a<b;return v[a].se<v[b].se;};sort(all(id),comp);vi rv(n);rep(i,n)rv[id[i]]=i;vi cur(n),tmp(n,-1),cur2(n),tmp2(n);rep(i,n)cur[i]=v[id[i]].fi;rep(i,n)tmp2[i]=v[id[i]].se;rep(i,n)cur2[i]=cur[i]*tmp2[i];segtree seg1(cur,tmp),seg2(cur2,tmp2);ll ans=inf;rep(i,n){ll dif=v[i].fi;if(i)dif-=v[i-1].fi;seg1.add(dif,0,n);seg2.add(-dif,0,n);seg1.update(rv[i],1);seg2.update(rv[i],-tmp2[rv[i]]);ll ok=0,ng=n;while(ng-ok>1){ll md=(ok+ng)/2;if(seg1.get(0,md)<seg1.get(md,n))ok=md;else ng=md;}ll cur=seg1.get(0,ok)*v[id[ok]].se-seg2.get(0,ok)+seg2.get(ok,n)-seg1.get(ok,n)*v[id[ok]].se;chmin(ans,cur);}out(ans);}