제출 #49760

#제출 시각아이디문제언어결과실행 시간메모리
49760hamzqq9Palembang Bridges (APIO15_bridge)C++14
22 / 100
323 ms14044 KiB
#include<bits/stdc++.h> #define lf double #define ll long long #define cc pair<char,char> #define ull unsigned ll #define ii pair<int,int> #define li pair<ll,int> #define iii pair<int,ii> #define iiii pair<ii,ii> #define iiii2 pair<int,iii> #define lii pair<ll,ii> #define lolo pair<ll,ll> #define heap priority_queue #define mp make_pair #define st first #define nd second #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define all(x) x.begin(),x.end() #define len(x) strlen(x) #define sz(x) (int) x.size() #define orta ((bas+son)/2) #define min3(x,y,z) min(min(x,y),z) #define max3(x,y,z) max(max(x,y),z) #define umin(x,y) x=min(x,y) #define umax(x,y) x=max(x,y) #define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" " #define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar() #define MOD 998244353 #define inf 1000000000 #define M 10000002 #define N 100005 #define LOG 40 #define magic 100 #define KOK 250 #define EPS 0.0025 #define pw(x) ((1ll)<<(x)) #define PI 3.1415926535 using namespace std; int sz,n,k,x1,x2; ll ans=inf,pre[N],suf[N],Sum[N*8],add; int Ok[N*8],tut[N*2]; vector<ii> seg; char c1,c2; void clear() { memset(Sum,0,sizeof(Sum)); memset(Ok,0,sizeof(Ok)); } ll getsum(int node,int bas,int son,int x,int y) { if(bas>y || son<x) return 0; if(bas>=x && son<=y) return Sum[node]; return getsum(node*2,bas,orta,x,y)+getsum(node*2+1,orta+1,son,x,y); } int getkth(int node,int bas,int son,int k) { if(bas==son) return bas; if(Ok[node*2]>=k) return getkth(node*2,bas,orta,k); return getkth(node*2+1,orta+1,son,k-Ok[node*2]); } void up(int node,int bas,int son,int x) { if(bas>x || son<x) return ; if(bas==x && son==x) { Sum[node]=tut[bas]; Ok[node]=1; return ; } up(node*2,bas,orta,x); up(node*2+1,orta+1,son,x); Sum[node]=Sum[node*2]+Sum[node*2+1]; Ok[node]=Ok[node*2]+Ok[node*2+1]; } void compress() { vector<iii> v; for(int i=0;i<sz;i++) { v.pb({seg[i].st,{i,0}}); v.pb({seg[i].nd,{i,1}}); } sort(all(v)); for(int i=0;i<2*sz;i++) { tut[i+1]=v[i].st; if(v[i].nd.nd) { seg[v[i].nd.st].nd=i+1; } else { seg[v[i].nd.st].st=i+1; } } } int main() { #if 0 freopen("input.txt","r",stdin); #endif scanf("%d %d",&k,&n); for(int i=1;i<=n;i++) { scanf(" %c %d %c %d",&c1,&x1,&c2,&x2); if(c1==c2) add+=abs(x1-x2); else { if(x1>x2) swap(x1,x2); seg.pb({x1,x2}); } } sort(all(seg),[](ii x,ii y) { return x.st+x.nd<y.st+y.nd; }); sz=sz(seg); compress(); for(int i=0;i<sz;i++) { up(1,1,2*sz,seg[i].st); up(1,1,2*sz,seg[i].nd); int plc=getkth(1,1,2*sz,i+1); ll dec=getsum(1,1,2*sz,1,plc); ll add=getsum(1,1,2*sz,plc+1,2*sz); pre[i+1]=add-dec; } clear(); reverse(all(seg)); for(int i=0;i<sz;i++) { up(1,1,2*sz,seg[i].st); up(1,1,2*sz,seg[i].nd); int plc=getkth(1,1,2*sz,i+1); ll dec=getsum(1,1,2*sz,1,plc); ll add=getsum(1,1,2*sz,plc+1,2*sz); suf[i+1]=add-dec; } if(k==2) { for(int i=1;i<sz;i++) { umin(ans,pre[i]+suf[sz-i]); } } else { ans=pre[sz]; } printf("%lld",add+ans+sz); }

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

bridge.cpp: In function 'int main()':
bridge.cpp:135:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&k,&n);
  ~~~~~^~~~~~~~~~~~~~~
bridge.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %c %d",&c1,&x1,&c2,&x2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...