/*
weak weak we ak we akwea weak we
weak weak we ak weak weak we ak we
weakweak we ak wea ak we akwe
wea we ak we ak we akwe
wea we ak we ak we akwe
wea eak weak we ak we ak we
wea wea ak we ak weak we
we
we ak wea ak weak we
we ak wea weak wea eak we
we ak we ak wea wea we we
weak we ak we we we we
we we ak we we we we
we wea weak wea wea weak weak
weak wea akw weak weak
*/
using namespace std;
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <bitset>
#include <set>
#include <string>
#include <stack>
#include <iomanip>
#include <map>
#include <memory.h>
#include <deque>
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<LL>> vvl;
#define pb push_back
#define F first
#define S second
#define mid (LB+RB)/2
#define mkp make_pair
//iterators
#define iter(x) x.begin(),x.end()
#define aiter(a,n) a,a+n
//loops
#define REP(n) for (int ___=n;___--;)
#define REP0(i,n) for (int i=0;i<n;++i)
#define REP1(i,n) for (int i=1;i<=n;++i)
#define FOR(i,b,l,k) for (int i=b;i!=l;i+=k)
#define MEM(e,val) memset (e,val,sizeof(e))
#define FE(i,v) for (auto i:v)
/*
yungyao so weeeeeeeeeeeeeeeeeeeeeeeeeeak
8e7 so dian
FHVirus so dian
youou so dian
KYW so dian
hubert so dian
jass so dian
tingyu so dian
panda so dian
*/
//IO
#include <cstdio>
#include <iostream>
#include <fstream> //mainly for USACO, sometimes for benjidabiao
#define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
//testing some stuff, still under construction
//a lot more useful while debug
inline void print(vector <int> v){
for (auto i:v)
cout << i << ' ';
cout << '\n';
}
inline void print(vector <int> v,char sep,char end){
for (auto i:v)
cout << i << sep;
cout << end;
}
//pbds
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
*/
//constants
#include <climits>
const int maxn = 0,mod = 0;
//workspace
struct Node{
LL x;
bool left;
LL preR,postL;
int preRcnt,postLcnt;
bool operator<(Node p){return x < p.x;}
Node(int x,bool left):
x(x),left(left),preR(left ? 0 : x),postL(left ? x : 0),preRcnt(!left),postLcnt(left){}
};
LL ans_base;
inline void solve1(){
int n;
cin >> n;
vector <Node> v;
REP(n){
char a,b; int x,y;
cin >> a >> x >> b >> y;
ans_base += max(x,y) - min(x,y);
if (a != b){
++ans_base;
v.pb(Node(min(x,y),true));
v.pb(Node(max(x,y),false));
}
}
if (v.empty()) {cout << ans_base; return;}
sort (iter(v));
for (int i=1;i<v.size();++i){
v[i].preR += v[i-1].preR;
v[i].preRcnt += v[i-1].preRcnt;
}
for (int i=v.size()-1;i--;){
v[i].postL += v[i+1].postL;
v[i].postLcnt += v[i+1].postLcnt;
}
LL ans = LLONG_MAX;
for (auto [x,t,pr,pl,prcnt,plcnt]:v){
ans = min(ans,x * prcnt - pr + pl - x * plcnt);
}
cout << ans_base + ans * 2;
}
inline void solve2(){
}
signed main(){
theyRSOOOOOOOOODIAN
//for (int ;cin;)//use in multi-testcases and end in EOF problems
//int t,i=1;for (cin >> t;i<=t;++i)//use in multi-testcases problems
//cout << "Case #" << i << ": ",//use in Google, FB competitions
int k;
cin >> k;
if (k == 1) solve1();
else solve2();
return 0;
}
Compilation message
bridge.cpp: In function 'void solve1()':
bridge.cpp:135:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (int i=1;i<v.size();++i){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
460 KB |
Output is correct |
| 10 |
Correct |
1 ms |
460 KB |
Output is correct |
| 11 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
456 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
460 KB |
Output is correct |
| 10 |
Correct |
1 ms |
456 KB |
Output is correct |
| 11 |
Correct |
1 ms |
460 KB |
Output is correct |
| 12 |
Correct |
47 ms |
11392 KB |
Output is correct |
| 13 |
Correct |
62 ms |
12456 KB |
Output is correct |
| 14 |
Correct |
46 ms |
11788 KB |
Output is correct |
| 15 |
Correct |
35 ms |
6496 KB |
Output is correct |
| 16 |
Correct |
49 ms |
11976 KB |
Output is correct |
| 17 |
Correct |
47 ms |
12364 KB |
Output is correct |
| 18 |
Correct |
53 ms |
12124 KB |
Output is correct |
| 19 |
Correct |
61 ms |
12444 KB |
Output is correct |
| 20 |
Correct |
53 ms |
12032 KB |
Output is correct |
| 21 |
Correct |
57 ms |
12344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
