oj.uz

답안 #969623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969623 2024-04-25T11:12:35 Z batsukh2006 Palembang Bridges (APIO15_bridge) C++17
22 / 100
 238 ms 20140 KB 
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
#include<numeric>
#include<tuple>
#include<bitset>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD 1000000007
#define int long long
#define ss second
#define ff first
#define endl '\n'
#define ordered_set tree<pair<int, int>, null_type, less_equal<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update>
signed main(){
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int k,n; cin>>k>>n;
    int sum=0;
    vector<pair<int,int> > v,d;
    for(int i=0,j=0; i<n; i++){
    	int s,t;
    	char p,q;
    	cin>>p>>s>>q>>t;
    	if(p==q){
    		sum+=abs(s-t);
    	}else{
    		sum++;
    		v.push_back({s,j});
    		v.push_back({t,j});
    		d.push_back({s,t});
    		j++;
    	}
    }
    if(v.empty()){
    	cout<<sum;
    	return 0;
    }
    int sl=0,sr=0;
    ordered_set f,s;
    vector<bool> vis(n);
    sort(v.begin(),v.end());
    for(int i=0; i<v.size(); i++) s.insert({v[i].ff,v[i].ss});
    int ml=(*s.find_by_order(1)).ff;
	int mr=(*s.find_by_order(s.size()/2)).ff;
    for(int i=0; i<v.size(); i++) sr+=abs(mr-v[i].ff);
    int res=sl+sr;
    if(k==1){
	    cout<<res+sum;
	}else{
		for(int i=0; i<v.size(); i++){
			if(!vis[v[i].ss]){
				vis[v[i].ss]=1;
				s.erase(s.upper_bound({d[v[i].ss].ff,v[i].ss}));
				s.erase(s.upper_bound({d[v[i].ss].ss,v[i].ss}));
				f.insert({d[v[i].ss].ff,v[i].ss});
				f.insert({d[v[i].ss].ss,v[i].ss});
				int fh=f.size()/2,sh=s.size()/2;
				int pl=(*f.find_by_order(fh)).ff;
				int pr=(*s.find_by_order(sh)).ff;
				if(f.size()==2) ml=pl;
				sl+=abs(d[v[i].ss].ff-ml);
				sl+=abs(d[v[i].ss].ss-ml);
				sl+=fh*(pl-ml);
				sl-=(f.size()-fh)*(pl-ml);
				sr-=abs(d[v[i].ss].ff-mr);
				sr-=abs(d[v[i].ss].ss-mr);
				sr+=sh*(pr-mr);
				sr-=(s.size()-sh)*(pr-mr);
				ml=pl;
				mr=pr;
				res=min(res,sl+sr);
			}
//			res=min(res,sl+sr);
//			cout<<sl<<' '<<sr<<endl;
		}
		cout<<res+sum;
	}
    return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:64:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0; i<v.size(); i++) s.insert({v[i].ff,v[i].ss});
      |                  ~^~~~~~~~~
bridge.cpp:67:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0; i<v.size(); i++) sr+=abs(mr-v[i].ff);
      |                  ~^~~~~~~~~
bridge.cpp:72:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=0; i<v.size(); i++){
      |                ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 520 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 226 ms 18272 KB Output is correct
13 Correct 230 ms 19776 KB Output is correct
14 Correct 207 ms 16952 KB Output is correct
15 Correct 88 ms 11692 KB Output is correct
16 Correct 238 ms 19264 KB Output is correct
17 Correct 220 ms 19772 KB Output is correct
18 Correct 227 ms 19512 KB Output is correct
19 Correct 236 ms 19768 KB Output is correct
20 Correct 235 ms 20140 KB Output is correct
21 Correct 230 ms 19636 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -