oj.uz

답안 #1050154

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050154 2024-08-09T07:45:07 Z 정희우(#11049) 별자리 3 (JOI20_constellation3) C++17
0 / 100
 10 ms 27484 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;
using pil = pair<int,lint>;

const int MAX_N=200010;

struct Setobj
{
    set<pil> s;
    lint cshift;
    Setobj()
    {
        s.insert({0,0});
        cshift=0;
    }
    void push_star(int h,lint c)
    {
        cshift+=c;
        pil o={h,-c};
        auto it=s.upper_bound(o);
        if(it!=s.begin() && prev(it)->second<=o.second)return;
        while(it!=s.end() && it->second>=o.second)
        {
            auto del=it++;
            s.erase(del);
        }
        s.insert(o);
    }
    void merge_(const Setobj &so,int h1,int h2)
    {
        lint cs1=cshift+so.cshift,cs2=cs1;
        if(h1<h2)
        {
            cs1+=so.s.begin()->second;
            cs2+=prev(s.lower_bound({h2,0}))->second;
        }
        if(h1>h2)
        {
            cs1+=prev(so.s.lower_bound({h1,0}))->second;
            cs2+=s.begin()->second;
        }
        for(auto o : so.s)
        {
            o.second+=cs2-cs1;
            auto it=s.upper_bound(o);
            if(it!=s.begin() && prev(it)->second<=o.second)continue;
            while(it!=s.end() && it->second>=o.second)
            {
                auto del=it++;
                s.erase(del);
            }
            s.insert(o);
        }
        cshift=cs1;
    }
    lint value()
    {
        return cshift+prev(s.end())->second;
    }
};

int n,m;
int arr[MAX_N],l[MAX_N],r[MAX_N];
pii sorth[MAX_N];
int seti[MAX_N];
Setobj st[MAX_N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> arr[i];
        sorth[i]={arr[i],i};
        seti[i]=i;
    }
    sort(sorth+1,sorth+1+n);
    vector<pii> mxh={{0,MAX_N}};
    arr[0]=arr[n+1]=MAX_N;
    for(int i=1;i<=n;i++)
    {
        while(mxh.back().second<arr[i])mxh.pop_back();
        l[i]=mxh.back().first;
        mxh.push_back({i,arr[i]});
    }
    mxh={{n+1,MAX_N}};
    for(int i=n;i>=1;i--)
    {
        while(mxh.back().second<arr[i])mxh.pop_back();
        r[i]=mxh.back().first;
        mxh.push_back({i,arr[i]});
    }
    cin >> m;
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        cin >> x >> y >> c;
        st[x].push_star(y,c);
    }
    for(int i=1;i<n;i++)
    {
        int u=sorth[i].second,v;
        if(arr[l[u]]<arr[r[u]])
        {
            v=l[u];
            if(arr[r[v]]<=arr[r[u]])r[v]=r[u];
        }
        else
        {
            v=r[u];
            if(arr[l[v]]<=arr[l[u]])l[v]=l[u];
        }
        if(st[seti[u]].s.size()<st[seti[v]].s.size())swap(u,v);
        st[seti[u]].merge_(st[seti[v]],arr[u],arr[v]);
        seti[v]=seti[u];
    }
    cout << st[seti[sorth[n].second]].value();
    return 0;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 27484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 27484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 27484 KB Output isn't correct
2 Halted 0 ms 0 KB -