Submission #882965

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
882965	2023-12-04T09:28:38 Z	tolbi	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	508 ms	43276 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	2 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	3 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	2 ms	604 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	2 ms	600 KB	Output is correct
5	Correct	3 ms	600 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	2 ms	600 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	2 ms	604 KB	Output is correct
12	Correct	95 ms	29780 KB	Output is correct
13	Correct	473 ms	42348 KB	Output is correct
14	Correct	258 ms	29872 KB	Output is correct
15	Correct	244 ms	22916 KB	Output is correct
16	Correct	105 ms	29780 KB	Output is correct
17	Correct	261 ms	42160 KB	Output is correct
18	Correct	250 ms	43276 KB	Output is correct
19	Correct	275 ms	41648 KB	Output is correct
20	Correct	94 ms	29780 KB	Output is correct
21	Correct	270 ms	42160 KB	Output is correct

Subtask #3

9.0 / 9.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	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 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	348 KB	Output is correct
2	Correct	1 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	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	344 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	684 KB	Output is correct
15	Correct	2 ms	604 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	600 KB	Output is correct
18	Correct	1 ms	600 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	2 ms	604 KB	Output is correct
21	Correct	2 ms	604 KB	Output is correct
22	Correct	3 ms	604 KB	Output is correct
23	Correct	1 ms	600 KB	Output is correct
24	Correct	2 ms	604 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	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 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	604 KB	Output is correct
15	Correct	3 ms	600 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	2 ms	604 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	2 ms	600 KB	Output is correct
21	Correct	2 ms	600 KB	Output is correct
22	Correct	2 ms	604 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	2 ms	604 KB	Output is correct
25	Correct	89 ms	29776 KB	Output is correct
26	Correct	112 ms	29632 KB	Output is correct
27	Correct	448 ms	41136 KB	Output is correct
28	Correct	508 ms	42208 KB	Output is correct
29	Correct	479 ms	42216 KB	Output is correct
30	Correct	215 ms	21704 KB	Output is correct
31	Correct	92 ms	29632 KB	Output is correct
32	Correct	288 ms	42300 KB	Output is correct
33	Correct	258 ms	42308 KB	Output is correct
34	Correct	283 ms	41624 KB	Output is correct
35	Correct	96 ms	29684 KB	Output is correct
36	Correct	296 ms	42104 KB	Output is correct
37	Correct	91 ms	29632 KB	Output is correct