Submission #882964

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
882964	2023-12-04T09:27:29 Z	vjudge1	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	513 ms	44624 KB

bridge

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
#define int long long
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
map<int,int> whatthefuckneyapionuzabisizdunyayaasirisinirlendimbunebicimproblem;
struct SegTree{
	vector<pair<int,int>> segtree;
	SegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,{0,0});
	}
	void push(int x){
		int l = 0, r = segtree.size()/2;
		int node = 0;
		int pos = whatthefuckneyapionuzabisizdunyayaasirisinirlendimbunebicimproblem[x];
		while (l<r){
			int mid = l+(r-l)/2;
			segtree[node].first+=x;
			segtree[node].second++;
			if (l==r) break;
			if (mid>=pos){
				r=mid;
				node=node*2+1;
			}
			else {
				l=mid+1;
				node=node*2+2;
			}
		}
		segtree[node].first+=x;
		segtree[node].second++;
	}
	void erase(int x){
		int l = 0, r = segtree.size()/2;
		int node = 0;
		int pos = whatthefuckneyapionuzabisizdunyayaasirisinirlendimbunebicimproblem[x];
		while (l<r){
			int mid = l+(r-l)/2;
			segtree[node].first-=x;
			segtree[node].second--;
			if (l==r) break;
			if (mid>=pos){
				r=mid;
				node=node*2+1;
			}
			else {
				l=mid+1;
				node=node*2+2;
			}
		}
		segtree[node].first-=x;
		segtree[node].second--;
	}
	int median(){
		int l = 0, r = segtree.size()/2;
		int node = 0;
		int k = segtree[node].second/2;
		while (l<r){
			int mid = l+(r-l)/2;
			int left = segtree[node*2+1].second;
			if (left>=k){
				node=node*2+1;
				r=mid;
			}
			else {
				k-=left;
				node=node*2+2;
				l=mid+1;
			}
		}
		return l;
	}
	pair<int,int> query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
		if (r==-1){
			r=segtree.size()/2, node=0;
		}
		if (l>=tarl && r<=tarr) return segtree[node];
		if (l>tarr || r<tarl) return {0,0};
		int mid = l+(r-l)/2;
		pair<int,int> lnode = query(tarl, tarr, l, mid, node*2+1);
		pair<int,int> rnode = query(tarl, tarr, mid+1, r, node*2+2);
		return {lnode.first+rnode.first,lnode.second+rnode.second};
	}
};
int LIMN;
vector<int> compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz;
struct Solution{
	SegTree segtree,ls,rs;
	Solution():segtree(LIMN),ls(LIMN),rs(LIMN){}
	void push(int l, int r){
		ls.push(l);
		rs.push(r);
		segtree.push(l);
		segtree.push(r);
	}
	void erase(int l, int r){
		ls.erase(l);
		rs.erase(r);
		segtree.erase(l);
		segtree.erase(r);
	}
	int query(){
		int x = compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz[segtree.median()];
		int pl = whatthefuckneyapionuzabisizdunyayaasirisinirlendimbunebicimproblem[x];
		pair<int,int> left = rs.query(0,pl);
		pair<int,int> right = ls.query(pl,LIMN-1);
		return (left.second*x-left.first+right.first-right.second*x)*2;
	}
};
int32_t main(){
	ios;
	int t=1;
	int tno = 0;
	if (!t) cin>>t;
	while (t-(tno++)){
		deci(k);deci(n);
		LIMN = 2*n;
		vector<pair<int,int>> segment;
		int ans = 0;
		for (int i = 0; i < n; i++){
			char a,c;
			int b,d;
			cin>>a>>b>>c>>d;
			ans+=abs(b-d);
			if (a!=c){
				ans++;
				segment.push_back({min(b,d),max(b,d)});
				compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz.push_back(b);
				compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz.push_back(d);
			}
		}
		sortarr(compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz);
		for (int i = 0; i < compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz.size(); i++){
			whatthefuckneyapionuzabisizdunyayaasirisinirlendimbunebicimproblem[compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz[i]]=i;
		}
		n=segment.size();
		vector<int> arr(n+1,0);
		vector<int> barr(n+1,0);
		Solution soln;
		sort(segment.begin(), segment.end(), [&](pair<int,int> a, pair<int,int> b){
			return (a.first+a.second)<(b.first+b.second);
		});
		for (int i = 1; i <= n; i++){
			soln.push(segment[i-1].first,segment[i-1].second);
			arr[i]=soln.query();
		}
		for (int i = 1; i <= n; i++){
			barr[n-i+1]=soln.query();
			soln.erase(segment[i-1].first,segment[i-1].second);
		}
		if (k==1) ans+=arr[n];
		else {
			int crr = arr[0]+barr[n];
			for (int i = 0; i <= n; i++){
				crr=min(arr[i]+barr[n-i],crr);
			}
			ans+=crr;
		}
		cout<<ans<<endl;
	}
}

Compilation message

bridge.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
bridge.cpp: In function 'int32_t main()':
bridge.cpp:163:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |   for (int i = 0; i < compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct
5	Correct	2 ms	604 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	2 ms	604 KB	Output is correct
8	Correct	2 ms	604 KB	Output is correct
9	Correct	2 ms	820 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	2 ms	604 KB	Output is correct
5	Correct	3 ms	604 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	2 ms	604 KB	Output is correct
8	Correct	2 ms	604 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	3 ms	604 KB	Output is correct
12	Correct	88 ms	29628 KB	Output is correct
13	Correct	513 ms	42312 KB	Output is correct
14	Correct	252 ms	29928 KB	Output is correct
15	Correct	228 ms	22724 KB	Output is correct
16	Correct	91 ms	29632 KB	Output is correct
17	Correct	278 ms	42304 KB	Output is correct
18	Correct	283 ms	42164 KB	Output is correct
19	Correct	275 ms	41644 KB	Output is correct
20	Correct	91 ms	29620 KB	Output is correct
21	Correct	270 ms	42304 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	460 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	456 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct

Subtask #4

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	464 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Correct	2 ms	604 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	600 KB	Output is correct
20	Correct	2 ms	604 KB	Output is correct
21	Correct	2 ms	604 KB	Output is correct
22	Correct	2 ms	600 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	2 ms	728 KB	Output is correct

Subtask #5

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	3 ms	348 KB	Output is correct
5	Correct	0 ms	460 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	2 ms	720 KB	Output is correct
15	Correct	3 ms	604 KB	Output is correct
16	Correct	1 ms	588 KB	Output is correct
17	Correct	1 ms	672 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	3 ms	604 KB	Output is correct
21	Correct	2 ms	604 KB	Output is correct
22	Correct	2 ms	844 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	2 ms	604 KB	Output is correct
25	Correct	88 ms	30464 KB	Output is correct
26	Correct	117 ms	30748 KB	Output is correct
27	Correct	469 ms	42916 KB	Output is correct
28	Correct	466 ms	44460 KB	Output is correct
29	Correct	488 ms	44624 KB	Output is correct
30	Correct	202 ms	23112 KB	Output is correct
31	Correct	94 ms	31280 KB	Output is correct
32	Correct	263 ms	44620 KB	Output is correct
33	Correct	256 ms	44244 KB	Output is correct
34	Correct	280 ms	44280 KB	Output is correct
35	Correct	94 ms	31664 KB	Output is correct
36	Correct	285 ms	44384 KB	Output is correct
37	Correct	85 ms	30560 KB	Output is correct