이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
void fastIO(){
ios_base::sync_with_stdio(false);
cin.tie(0);
}
typedef long long ll;
typedef pair<int, int> pii;
#define ff first
#define ss second
int K, N, A[100100], B[100100], cnt = 0;
ll same = 0;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
int comb[200100];
ll solve1(){
for (int i = 1; i <= cnt; i++){
comb[2*i-1] = A[i];
comb[2*i] = B[i];
}
sort(comb+1, comb+2*cnt+1);
int mid = comb[cnt];
ll ans = same+cnt;
for (int i = 1; i <= cnt; i++){
ans += abs(A[i]-mid)+abs(B[i]-mid);
}
return ans;
}
pii comb2[200100];
pii loc[200100];
pii v[200100];
void solve2(){
for (int i = 1; i <= cnt; i++){
comb2[2*i-1] = {A[i], i};
comb2[2*i] = {B[i], i};
}
sort(comb2+1, comb2+1+2*cnt);
for (int i = 1; i <= 2*cnt; i++){
if (loc[comb2[i].ss].ff == 0){
loc[comb2[i].ss].ff = i;
} else {
loc[comb2[i].ss].ss = i;
}
}
int bl = 0, br = 0, bml = 0;//bl is both left, br is both right, bml is middle but goes to left bridge
set<pair<int, int> > s; //sum index
int r = 2;
ll cur = 0, best = LINF;
for (int i = 1; i <= cnt; i++){
if (loc[i].ff > 2 && loc[i].ss > 2) br++;
cur += abs(A[i]-comb2[2].ff)+abs(B[i]-comb2[2].ff);
}
best = cur;
//cout << "bl br bml size cur\n";
for (int i = 1; i <= 2*cnt-2; i++){//i represents the left pointer
//cout << i << ":\n";
int lpos = comb2[i].ff;
ll pre = cur;
bool stop = false;
while (r < 2*cnt){
//deal with br
ll ncur = cur;
ncur -= (ll)2*br*(comb2[r+1].ff-comb2[r].ff);
//deal with set
int numerase = 0;
//vector<pair<int, int> > v;
int vind = 1;
for (pair<int, int> x : s){
int distl = x.ff-2*lpos;
int distr = 2*(comb2[r].ff-lpos)-distl;
int distnr = 2*(comb2[r+1].ff-lpos)-distl;
if (distnr >= distl){
ncur += distl-distr;
numerase++;
//v.push_back(x);
v[vind++] = x;
} else {
break;
}
}
for (int x = 1; x <= numerase; x++) s.erase(s.begin());
ncur += (ll)2*(int)s.size()*(comb2[r+1].ff-comb2[r].ff);
if (ncur > pre || stop){
if (r > i+1){
//revert
for (int k = 1; k < vind; k++) s.insert(v[k]);
break;
} else {
stop = true;
}
}
cur = ncur;
if (loc[comb2[r+1].ss].ff == r+1){
br--;
}
if (loc[comb2[r+1].ss].ss == r+1){
if (loc[comb2[r+1].ss].ff > i){
int ind = comb2[r+1].ss;
int distl = A[ind]+B[ind]-2*lpos;
int distr = 2*(comb2[r+1].ff-lpos)-distl;
if (distr < distl)
s.insert(make_pair(A[ind]+B[ind], ind));
else
bml++;
}
}
//deal with bml
bml += numerase;
r++;
best = min(best, cur);
//cout << bl << " " << br << " " << bml << " " << (int)s.size() << " " << cur << "\n";
pre = cur;
}
/*cout << bl << " " << (int)s.size() << " " << bml << "\n";
for (pii x : s) cout << x.ff << " " << x.ss << "\n";
cout << "\n";*/
//now increment the l pointer
//deal with bl
cur += (ll)2*bl*(comb2[i+1].ff-comb2[i].ff);
if (loc[comb2[i+1].ss].ss == i+1){
bl++;
}
//deal with set
cur -= (ll)2*bml*(comb2[i+1].ff-comb2[i].ff);
//first erase
if (loc[comb2[i+1].ss].ff == i+1){
if (loc[comb2[i+1].ss].ss <= r){
//cout << "HElo\n";
int ind = comb2[i+1].ss;
int distl = A[ind]+B[ind]-2*lpos;
int distnl = A[ind]+B[ind]-2*comb2[i+1].ff;
int distr = 2*(comb2[r].ff-comb2[i].ff)-distl;
//cout << A[ind] << " " << B[ind] << "\n";
//cout << distl << " " << distr << "\n";
if (distr < distl){
cur += distnl-distr;
s.erase({A[ind]+B[ind], ind});
} else {
bml--;
}
}
}
int numerase = 0;
int nlpos = comb2[i+1].ff;
for (pair<int, int> x : s){
// int distl = x.ff-2*lpos;
int distnl = x.ff-2*nlpos;
int distr = 2*(comb2[r].ff-nlpos)-distnl;
if (distr >= distnl){
cur += distnl-distr;
numerase++;
} else {
break;
}
}
for (int x = 1; x <= numerase; x++) s.erase(s.begin());
bml += numerase;
best = min(best, cur);
//cout << "ed: " << r << " " << cur << "\n";
//cout << "Ed: ";
//cout << bl << " " << br << " " << bml << " " << (int)s.size() << " " << cur << "\n";
}
cout << best+same+cnt << "\n";
}
const int BUFSIZE=20<<20;//20MB
char Buf[BUFSIZE+1],*buf=Buf;
//fread(Buf,1,BUFSIZE,stdin); 在读入之前写这句话 任何整数
template<class T>
void scan(T&a){
int sgn=1;
for(a=0;*buf<'0'||*buf>'9';buf++)if(*buf=='-')sgn=-1;
while(*buf>='0'&&*buf<='9'){a=a*10+(*buf-'0');buf++;}
a*=sgn;
}
//char strtr[300100];
char aaa[300100], bbb[300100];
int tot;
void scanString(char *s){
tot=0;
for(;(*buf<'A'||*buf>'Z');buf++);
while(*buf>='A'&&*buf<='Z'){s[tot++]=*buf;buf++;}
}
signed main(){
fread(Buf,1,BUFSIZE,stdin);
//fastIO();
scan(K); scan(N);
//cin >> K >> N;
for (int i = 1; i <= N; i++){
string ca, cb;
int a, b;
scanString(aaa); scan(a); scanString(bbb); scan(b);
//cin >> ca >> a >> cb >> b;
if (aaa[0] == bbb[0]){
same += abs(b-a);
} else {
if (aaa[0] == 'A'){
A[++cnt] = a;
B[cnt] = b;
} else {
A[++cnt] = b;
B[cnt] = a;
}
}
}
if (K == 1){
cout << solve1() << "\n";
} else {
solve2();
}
}
컴파일 시 표준 에러 (stderr) 메시지
bridge.cpp: In function 'int main()':
bridge.cpp:203:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
203 | fread(Buf,1,BUFSIZE,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# | 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... |