Submission #1115075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115075		8pete8	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	128 ms	19248 KiB

kyoto

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=998244353,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30;
int n,k,m,q;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);
}
struct node{
	int c0,c1;
	bool operator<(node a)const{return (c0*a.c1)<(c1*a.c0);}
};
int A[mxn+10],B[mxn+10],P[mxn+10],pa[mxn+10],vis[mxn+10];
node have[mxn+10];
int find(int u){
	return ((u==pa[u])?u:pa[u]=find(pa[u]));
}
void merge(int a,int b){
	a=find(a),b=find(b);
	if(a==b)return;
    pa[b]=a;
}
int32_t main(){
    fastio
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>A[i];
	for(int i=1;i<=m;i++)cin>>B[i];
    for(int i=0;i<=n+m+1;i++)pa[i]=i;
	priority_queue<pair<node,int>>pq;
	int ans=0;
	for(int i=2;i<=n;i++){
		P[i]=i-1;
        ans-=A[i-1];//subtract overcount inversion -> constant
		have[i]=(node){1,A[i]-A[i-1]};
		pq.push({have[i],i});
	}
	for(int i=2;i<=m;i++){
		if(i==2)P[i+n]=0;
		else P[i+n]=i+n-1;
        ans-=B[i-1];
		have[i+n]=(node){1,B[i]-B[i-1]};
		pq.push({have[i+n],i+n});
	}
    have[0].c0=2;
    have[0].c1=B[1]+A[1];
	while(!pq.empty()){
		int cur=pq.top().s;
		node x=pq.top().f;
		pq.pop();
		if(have[cur].c1!=x.c1||have[cur].c0!=x.c0)continue;
		if(vis[cur])continue;
		vis[cur]=1;
		ans+=have[find(P[cur])].c1*x.c0;
		have[find(P[cur])].c1+=x.c1;
		have[find(P[cur])].c0+=x.c0;
        merge((P[cur]),cur);
		if(find(P[cur])!=0)pq.push({have[find(P[cur])],find(P[cur])});
	}
	cout<<ans;
}
/*

*/

Compilation message (stderr)

kyoto.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
kyoto.cpp:37:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   37 | void setIO(string name){
      |                       ^
kyoto.cpp:44:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   44 |  bool operator<(node a)const{return (c0*a.c1)<(c1*a.c0);}
      |                        ^~~~~
kyoto.cpp:48:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   48 | int find(int u){
      |               ^
kyoto.cpp:51:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   51 | void merge(int a,int b){
      |                       ^
kyoto.cpp:56:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   56 | int32_t main(){
      |              ^
kyoto.cpp: In function 'void setIO(std::string)':
kyoto.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kyoto.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60