제출 #76778

#제출 시각아이디문제언어결과실행 시간메모리
76778born2rulePalembang Bridges (APIO15_bridge)C++14
22 / 100
363 ms39792 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ll long long #define db long double #define ii pair<int,int> #define vi vector<int> #define fi first #define se second #define sz(a) (int)(a).size() #define all(a) (a).begin(),(a).end() #define pb push_back #define mp make_pair #define FN(i, n) for (int i = 0; i < (int)(n); ++i) #define FEN(i,n) for (int i = 1;i <= (int)(n); ++i) #define rep(i,a,b) for(int i=a;i<b;i++) #define repv(i,a,b) for(int i=b-1;i>=a;i--) #define SET(A, val) memset(A, val, sizeof(A)) typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ; // order_of_key (val): returns the no. of values less than val // find_by_order (k): returns the kth largest element.(0-based) #define TRACE #ifdef TRACE #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void __f(const char* name, Arg1&& arg1){ cerr << name << " : " << arg1 << std::endl; } template <typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); } #else #define trace(...) #endif const int N=100005; map<int,vi> m1,m2; vi v; int st[N],en[N],cnt; int main() { std::ios::sync_with_stdio(false); cin.tie(NULL) ; cout.tie(NULL) ; int k,n; cin>>k>>n; ll sum=0; ll distpost=0,distpre=0,cntpost=0,cntpre=0; ll totsum=0; rep(i,1,n+1) { char x,y; int st,en; cin>>x>>st>>y>>en; if(st>en) swap(st,en); if(x==y) sum+=en-st; else { v.pb(st); v.pb(en); cnt++; m1[st].pb(cnt); m2[en].pb(cnt); ::st[cnt]=st; ::en[cnt]=en; cntpost++; distpost+=st; totsum+=en-st; } } sort(all(v)); v.erase(unique(all(v)),v.end()); ll ans=LLONG_MAX; for(int x:v) { ll curr=0; //add which have st and en after this curr+=(distpost-cntpost*x); //add which have st and en before this curr+=(cntpre*x-distpre); curr*=2; //add which have st before and en after curr+=totsum; for(int ind:m1[x])//these elements are starting here { distpost-=st[ind]; cntpost--; } for(int ind:m2[x])//these elements are ending here { distpre+=en[ind]; cntpre++; } ans=min(ans,curr+cnt); } if(ans==LLONG_MAX) ans=0; ans+=sum; cout<<ans<<endl; return 0 ; }
#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...