This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |