oj.uz

Submission #699923

# Submission time Handle Problem Language Result Execution time Memory
699923 2023-02-18T10:44:41 Z Abrar_Al_Samit Palembang Bridges (APIO15_bridge) C++17
0 / 100
 1 ms 212 KB 
#include<bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
void PlayGround() {
  int k, n;
  cin>>k>>n;

  int s[n], t[n];

  vector<int>pts;
  long long ans = 0;

  for(int i=0; i<n; ++i) {
    char p, q;
    cin>>p>>s[i]>>q>>t[i];
    if(s[i]>t[i]) swap(s[i], t[i]);
    if(p==q) {
      ans += t[i] - s[i];
      --i;
      --n;
    } else {
      pts.push_back(s[i]);
      pts.push_back(t[i]);
    }
  }


  sort(pts.begin(), pts.end());
  pts.resize(unique(pts.begin(), pts.end())-pts.begin());

  int m = pts.size();

  long long best = INF;
  for(int i=0; i<m; ++i) {
  	int x = pts[i];

  	long long cur = 0;
  	map<int,int>come, gone;
  	vector<pair<int,int>>bag;
  	for(int j=0; j<n; ++j) {
  		if(s[j]>x) {
  			bag.emplace_back(s[j], t[j]);
  			come[s[j]]++;
  			gone[t[j]]--;
  		}
  		cur += abs(s[j]-x) + abs(t[j]-x);
  	}

  	set<int>new_pts;
  	for(int j=i; j<m; ++j) {
  		new_pts.insert(pts[j]);
  	}

  	for(int j=0; j<bag.size(); ++j) {
  		int new_point = bag[j].second + bag[j].first - x;
  		gone[new_point]++;
  		new_pts.insert(new_point);
  	}

  	int c1 = 0, c2 = bag.size();
  	while(!new_pts.empty()) {
  		int y = *new_pts.begin();
  		new_pts.erase(y);

  		best = min(best, cur);
  		if(new_pts.empty()) break;

  		int next_point = *new_pts.begin();
  		if(gone.count(y)) c1 -= gone[y];
  		if(come.count(y)) c2 -= come[y];

  		long long len = next_point - y;

  		cur += -c2 * 2 * len + c1 * 2 * len;
  	}
  }	

  ans += best + n;
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Compilation message

bridge.cpp: In function 'void PlayGround()':
bridge.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for(int j=0; j<bag.size(); ++j) {
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -