oj.uz

Submission #117549

# Submission time Handle Problem Language Result Execution time Memory
117549 2019-06-16T14:23:50 Z ckodser Palembang Bridges (APIO15_bridge) C++14
63 / 100
 2000 ms 13632 KB 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
 
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 
 
using namespace :: std;
 
const ll maxn=2e5+500;
const ll inf=1e9+800;
 
 
vector<ll> comp;
ll fen[4][maxn];
 
void addFen(ll x,ll v,char c){
	for(x++;x<maxn;x+=(x&(-x))){
		fen[c][x]+=v;
	}
}
ll findFen(ll x,char c){
	ll ans=0;
	for(x++;x;x-=(x&(-x))){
		ans+=fen[c][x];
	}	
	return ans;
}
ll getVal(ll rx){
	ll x=lower_bound(comp.begin(),comp.end(),rx)-comp.begin();
	return (findFen(x,0)-findFen(x,2))*rx-findFen(x,1)+findFen(x,3);
}	
void add(pii a){
	ll sl=a.F;
	ll sr=a.S;
 
	ll l=lower_bound(comp.begin(),comp.end(),sl)-comp.begin();
	ll r=lower_bound(comp.begin(),comp.end(),sr)-comp.begin();
 
	addFen(r+1,1,0);
 
	addFen(r+1,sr,1);
 
	addFen(0,1,2);
	addFen(l,-1,2);
 
	addFen(0,sl,3);
	addFen(l,-sl,3);
}
ll getAns(){
	ll ans=inf*maxn;
	for(auto e:comp){
		ans=min(ans,getVal(e));
	}
	return ans;
}
void clearr(){
	memset(fen,0,sizeof fen);
}
 
 
ll n,k;
ll saf[maxn];
ll pre[maxn];
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	cin>>k>>n;
	ll sum=0;
	vector<pair<ll,pii> > vec;
	for(ll i=0;i<n;i++){
		char C,T;
		ll L,R;
		cin>>C>>L>>T>>R;
		if(R<L){
			swap(L,R);
		}
		sum+=(abs(R-L));
		if(C==T){
			n--;
			i--;
		}else{
			comp.pb(L);
			comp.pb(R);
			sum++;
			vec.pb(mp(L+R,mp(L,R)));
		}
	}
 	if(vec.size()==0){
		cout<<sum;
		return 0;
	}
	sort(comp.begin(),comp.end());
	auto it=unique(comp.begin(),comp.end());
	comp.resize(it-comp.begin());
 
	sort(vec.begin(),vec.end());
	clearr();
	for(ll i=0;i<(ll)vec.size();i++){
		pii e=vec[i].S;
		add(e);
		if(k==2){
			pre[i]=getAns();
		}
	}
	if(k==1){
		cout<<getAns()*2+sum<<endl;
		return 0;
	}
	clearr();
	for(ll i=(ll)vec.size()-1;i>=0;i--){
		pii e=vec[i].S;
		add(e);
		saf[i]=getAns();
	}
	ll ans=saf[0];
	for(ll i=1;i<n;i++){
		ans=min(ans,saf[i]+pre[i-1]);
	}
	cout<<2*ans+sum;
}

Compilation message

bridge.cpp: In function 'void addFen(long long int, long long int, char)':
bridge.cpp:76:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   fen[c][x]+=v;
        ^
bridge.cpp: In function 'long long int findFen(long long int, char)':
bridge.cpp:82:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   ans+=fen[c][x];
             ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 7 ms 6656 KB Output is correct
4 Correct 7 ms 6628 KB Output is correct
5 Correct 7 ms 6656 KB Output is correct
6 Correct 7 ms 6656 KB Output is correct
7 Correct 8 ms 6692 KB Output is correct
8 Correct 8 ms 6784 KB Output is correct
9 Correct 8 ms 6656 KB Output is correct
10 Correct 8 ms 6656 KB Output is correct
11 Correct 8 ms 6656 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 7 ms 6656 KB Output is correct
4 Correct 8 ms 6656 KB Output is correct
5 Correct 7 ms 6656 KB Output is correct
6 Correct 7 ms 6656 KB Output is correct
7 Correct 7 ms 6828 KB Output is correct
8 Correct 8 ms 6656 KB Output is correct
9 Correct 8 ms 6656 KB Output is correct
10 Correct 8 ms 6656 KB Output is correct
11 Correct 8 ms 6656 KB Output is correct
12 Correct 63 ms 10880 KB Output is correct
13 Correct 144 ms 11004 KB Output is correct
14 Correct 81 ms 11900 KB Output is correct
15 Correct 78 ms 10888 KB Output is correct
16 Correct 67 ms 12688 KB Output is correct
17 Correct 90 ms 13324 KB Output is correct
18 Correct 97 ms 12928 KB Output is correct
19 Correct 110 ms 13308 KB Output is correct
20 Correct 70 ms 12796 KB Output is correct
21 Correct 104 ms 13060 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 7 ms 6656 KB Output is correct
4 Correct 8 ms 6656 KB Output is correct
5 Correct 7 ms 6656 KB Output is correct
6 Correct 7 ms 6656 KB Output is correct
7 Correct 8 ms 6628 KB Output is correct
8 Correct 9 ms 6656 KB Output is correct
9 Correct 9 ms 6656 KB Output is correct
10 Correct 8 ms 6656 KB Output is correct
11 Correct 7 ms 6656 KB Output is correct
12 Correct 8 ms 6656 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 7 ms 6656 KB Output is correct
4 Correct 8 ms 6628 KB Output is correct
5 Correct 7 ms 6656 KB Output is correct
6 Correct 7 ms 6656 KB Output is correct
7 Correct 7 ms 6656 KB Output is correct
8 Correct 8 ms 6656 KB Output is correct
9 Correct 8 ms 6656 KB Output is correct
10 Correct 8 ms 6656 KB Output is correct
11 Correct 7 ms 6656 KB Output is correct
12 Correct 8 ms 6656 KB Output is correct
13 Correct 8 ms 6656 KB Output is correct
14 Correct 12 ms 6656 KB Output is correct
15 Correct 268 ms 6892 KB Output is correct
16 Correct 7 ms 6656 KB Output is correct
17 Correct 10 ms 6784 KB Output is correct
18 Correct 40 ms 6656 KB Output is correct
19 Correct 8 ms 6784 KB Output is correct
20 Correct 280 ms 6776 KB Output is correct
21 Correct 281 ms 6904 KB Output is correct
22 Correct 276 ms 6904 KB Output is correct
23 Correct 9 ms 6784 KB Output is correct
24 Correct 278 ms 6904 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 7 ms 6656 KB Output is correct
4 Correct 8 ms 6656 KB Output is correct
5 Correct 8 ms 6656 KB Output is correct
6 Correct 7 ms 6656 KB Output is correct
7 Correct 8 ms 6656 KB Output is correct
8 Correct 8 ms 6656 KB Output is correct
9 Correct 8 ms 6656 KB Output is correct
10 Correct 9 ms 6656 KB Output is correct
11 Correct 8 ms 6656 KB Output is correct
12 Correct 8 ms 6656 KB Output is correct
13 Correct 8 ms 6656 KB Output is correct
14 Correct 12 ms 6784 KB Output is correct
15 Correct 277 ms 6892 KB Output is correct
16 Correct 7 ms 6656 KB Output is correct
17 Correct 10 ms 6656 KB Output is correct
18 Correct 38 ms 6656 KB Output is correct
19 Correct 8 ms 6784 KB Output is correct
20 Correct 278 ms 6784 KB Output is correct
21 Correct 280 ms 6776 KB Output is correct
22 Correct 266 ms 6784 KB Output is correct
23 Correct 10 ms 6784 KB Output is correct
24 Correct 286 ms 7020 KB Output is correct
25 Correct 94 ms 13304 KB Output is correct
26 Correct 481 ms 13632 KB Output is correct
27 Execution timed out 2050 ms 12816 KB Time limit exceeded
28 Halted 0 ms 0 KB -