Submission #567005

#	Time	Username	Problem	Language	Result	Execution time	Memory
567005		tqbfjotld	Sightseeing in Kyoto (JOI22_kyoto)	C++14	0 / 100	1 ms	596 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 999999999999999999LL;

int arr1[100005];
int arr2[100005];

struct node{
    int s,e;
    pair<int,int> v;
    node *l,*r;
    node (int _s, int _e, bool arr){
        s = _s; e = _e;
        if (s==e){
            v = make_pair((arr?arr1:arr2)[s],s);
        }
        if (s!=e){
            l = new node(s,(s+e)/2,arr);
            r = new node((s+e)/2+1,e,arr);
            v = min(l->v,r->v);
        }
    }
    pair<int,int> qu(int a, int b){
        if (a<=s && e<=b){
            return v;
        }
        if (b<=(s+e)/2){
            return l->qu(a,b);
        }
        if (a>(s+e)/2){
            return r->qu(a,b);
        }
        return min(l->qu(a,b),r->qu(a,b));
    }
}*r1,*r2;

int recl(int a, int b){
    if (a==0) return arr1[0]*b;
    if (b==0) return arr2[0]*a;
    int opt1 = r1->qu(0,a-1).first*b-arr1[a]*b;
    int opt2 = r2->qu(0,b-1).first*a-arr2[b]*a;
    if (opt1<opt2){
        int newind = r1->qu(0,a-1).second;
        int res = recl(newind,b);
        return (a-newind)*arr2[b]+res;
    }
    else{
        int newind = r2->qu(0,b-1).second;
        int res = recl(a,newind);
        return (b-newind)*arr1[a]+res;
    }
}

int n,m;

int recr(int a, int b){
    if (a==n-1) return arr1[n-1]*(m-1-b);
    if (b==m-1) return arr2[m-1]*(n-1-a);
    int opt1 = r1->qu(a+1,n-1).first*(m-1-b)-arr1[a]*(m-1-b);
    int opt2 = r2->qu(b+1,m-1).first*(n-1-a)-arr2[b]*(n-1-a);
    if (opt1<opt2){
        int newind = r1->qu(a+1,n-1).second;
        int res = recr(newind,b);
        return (newind-a)*arr2[b]+res;
    }
    else{
        int newind = r2->qu(b+1,m-1).second;
        int res = recr(a,newind);
        return (newind-b)*arr1[a]+res;
    }
}

 main(){

    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<n; x++){
        scanf("%lld",&arr1[x]);
    }
    for (int x = 0; x<m; x++){
        scanf("%lld",&arr2[x]);
    }
    r1 = new node(0,n-1,true);
    r2 = new node(0,m-1,false);
    auto i1 = r1->qu(0,n-1);
    auto i2 = r2->qu(0,m-1);
    int ans = recl(i1.second,i2.second)+recr(i1.second,i2.second);
    printf("%lld",ans);
}

Compilation message (stderr)

kyoto.cpp:75:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 |  main(){
      |  ^~~~
kyoto.cpp: In function 'int main()':
kyoto.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
kyoto.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf("%lld",&arr1[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
kyoto.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%lld",&arr2[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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