oj.uz

Submission #951293

# Submission time Handle Problem Language Result Execution time Memory
951293 2024-03-21T14:56:39 Z hotboy2703 Sightseeing in Kyoto (JOI22_kyoto) C++14
0 / 100
 1 ms 604 KB 
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll MAXN = 1e5;
ll n[2];
ll a[2][MAXN+100];
struct frac{
    ll x,y;
    bool operator < (const frac &p)const{
        return (p.y * y < 0) ^ (x*p.y<p.x*y);
    }
};
set <pair <frac,ll> > seg[2];
set <ll> s[2];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n[0]>>n[1];
    for (ll j = 0;j < 2;j ++){
        for (ll i = 1;i <= n[j];i ++)cin>>a[j][i];
    }
    for (ll j = 0;j < 2;j ++){
        for (ll i = 1;i <= n[j];i ++){
            s[j].insert(i);
            if (i>1)seg[j].insert(MP(frac({a[j][i]-a[j][i-1],1}),i));
        }
    }
    ll ans = 0;
    while (sz(s[0]) > 1 && sz(s[1]) > 1){
        bool o = (*seg[0].rbegin()).fi < (*seg[1].rbegin()).fi;
        ll x = (*seg[o].rbegin()).se;
        seg[o].erase(*seg[o].rbegin());
        if (x==*s[o].rbegin()){
            auto tmp = s[o].find(x);
            ans += (x-*prev(tmp)) * a[!o][*s[!o].rbegin()];
        }
        else{
            if (x==*s[o].begin()){

            }
            else{
                auto tmp = s[o].find(x);
                ll x1 = *prev(tmp),x2 = *next(tmp);
                seg[o].insert(MP(frac({a[o][x2]-a[o][x1],x2-x1}),x2));
            }
        }
        s[o].erase(x);
    }
    if (sz(s[0])==1)ans += (*s[1].rbegin() - 1) * a[0][1];
    else ans += (*s[0].rbegin() - 1) * a[1][1];
    cout<<ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -