이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 l2;
//typedef long long l2;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<db,db,db> tdb;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef tuple<int,int,int,int,int> ti5;
typedef tuple<ll,ll,ll,ll> tl4;
typedef tuple<db,db,db,db> td4;
typedef vector<vector<ll>> mat;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //shuffle(a+1,a+1+n,rng)
uniform_int_distribution<> gen(1,100); //gen(rng)
//https://codeforces.com/contest/1264/submission/66344993 + 몇 가지 기능 직접 추가
ll modinv(ll a,ll m){
if(m==1) return 0;
a%=m;
if(a<0) a+=m;
if(a==1) return 1;
return m-modinv(m,a)*m/a;
}
template <int MOD_> struct modnum{
private:
int v;
public:
static const int MOD = MOD_;
modnum() : v(0) {}
modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
explicit operator int () const { return v; }
friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
modnum operator ~ () const {
modnum res;
res.v = modinv(v, MOD);
return res;
}
modnum& operator += (const modnum& o) {
v += o.v;
if (v >= MOD) v -= MOD;
return *this;
}
modnum& operator -= (const modnum& o) {
v -= o.v;
if (v < 0) v += MOD;
return *this;
}
modnum& operator *= (const modnum& o) {
v = int(ll(v) * ll(o.v) % MOD);
return *this;
}
modnum& operator /= (const modnum& o) {
return *this *= (~o);
}
modnum operator-() const { return modnum(-v); }
modnum& operator++() { return *this += 1; }
modnum operator++(int){ modnum tmp=*this; ++*this; return tmp; }
modnum& operator--() { return *this -= 1; }
modnum operator--(int){ modnum tmp=*this; --*this; return tmp; }
friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
friend modnum pow(modnum a, ll p) {
modnum ans = 1;
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans;
}
friend ostream& operator<<(std::ostream& os, const modnum& o)
{
os << o.v;
return os;
}
friend istream& operator>>(std::istream& is, modnum& o)
{
is >> o.v;
return is;
}
int get(){
return v;
}
};
const ll mod=1e9+7,inf=1e18;
using mi=modnum<mod>;
const int N=1e5+5,M=1e6+5;
int n,m,k,a[N],b[N],c[N];
ll res,ans,pfx[N],sfx[N],S;
priority_queue<int> S1;
priority_queue<int,vector<int>,greater<int>> S2;
void Insert(int x){
int L=S1.top(),R=S2.top();
if(L<=x&&x<=R){
if(S1.size()<S2.size()){
S1.push(x); S-=x;
}
else{
S2.push(x); S+=x;
}
} else if(x<L){
S1.push(x); S-=x;
if(S1.size()>S2.size()+1){
S2.push(S1.top()); S+=2*S1.top();
S1.pop();
}
} else{
S2.push(x); S+=x;
if(S2.size()>S1.size()+1){
S1.push(S2.top()); S-=2*S2.top();
S2.pop();
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>k>>m;
for(int i=1;i<=m;i++){
int A,B; char P,Q;
cin>>P>>A>>Q>>B;
if(P==Q){
res+=abs(A-B); continue;
}
a[++n]=A; b[n]=B; c[n]=n;
}
sort(c+1,c+1+n,[&](int X,int Y){
return a[X]+b[X]<a[Y]+b[Y];
});
for(int i=n;i>=1;i--){
if(i==n){
S1.push(min(a[c[i]],b[c[i]]));
S2.push(max(a[c[i]],b[c[i]]));
S=max(a[c[i]],b[c[i]])-min(a[c[i]],b[c[i]]);
} else{
Insert(a[c[i]]); Insert(b[c[i]]);
}
sfx[i]=S;
}
while(S1.size()) S1.pop();
while(S2.size()) S2.pop();
for(int i=1;i<n;i++){
if(i==1){
S1.push(min(a[c[i]],b[c[i]]));
S2.push(max(a[c[i]],b[c[i]]));
S=max(a[c[i]],b[c[i]])-min(a[c[i]],b[c[i]]);
} else{
Insert(a[c[i]]); Insert(b[c[i]]);
}
pfx[i]=S;
}
ans=inf;
if(k==1) ans=sfx[1];
else for(int i=0;i<n;i++) ans=min(ans,pfx[i]+sfx[i+1]);
cout<<ans+n+res;
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... |