oj.uz

답안 #1077230

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077230 2024-08-27T03:37:54 Z HorizonWest 모임들 (IOI18_meetings) C++17
19 / 100
 5500 ms 2392 KB 
#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <vector>
//#include "meetings.h"
using namespace std;

#define endl '\n'
#define db double
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const ll Max = 1e6 + 7, Inf = 1e16 + 7;


struct SegmentTree
{
    struct node
    {
        ll val;

        node(ll v = Inf)
        {
            val = v;
        }
    }; 

    vector <node> tree; int l;

    node merge(node a, node b)
    {
        return node(min(a.val, b.val));
    }

    void update(int k, int v)
    {   k++;
        k += (l - 1); tree[k] = node(v);
        for(k /= 2; k > 0; k /= 2)
            tree[k] = merge(tree[2*k], tree[2*k+1]);
    }

    node query(int k, int x, int y, int s, int e)
    {
        if(s > y || e < x)
            return node();
        if(s >= x && e <= y)
            return tree[k];

        int middle = (s + e) / 2;

        return merge(query(2*k, x, y, s, middle),
            query(2*k+1, x, y, middle + 1, e));
    }

    int query(int x, int y)
    {   x++; y++;
        node ans = query(1, x, y, 1, l);
        return ans.val;
    }

    SegmentTree(int n)
    {
        for(l = 1; l < n; (l <<= 1));
        tree.assign(2 * l, node());
    }
};

void clear_vec(vector <ll> &v){
    for(auto& u : v) u = 0;
}

vector<long long> minimum_costs(vector<int> _H, vector<int> L, vector<int> R) 
{
    int n = _H.size(), q = L.size();

    vector <ll> v(n), H(n); 

    for(int i = 0; i < n; i++){
        H[i] = _H[i];
    }

    auto F = [&](int l, int r) -> ll
    {
        priority_queue <pair<ll, ll>> h; 
        clear_vec(v);

        ll sum = 0;
        while(!h.empty()){
            h.pop();
        }
     
        for(int i = l; i <= r; i++){
            h.push({-H[i], 1}); sum += H[i];
            while (!h.empty())
            {
                ll x = abs(h.top().fs), w = h.top().sd; 
                if(H[i] > x){
                    h.pop();
                    ll tx = -h.top().fs, ty = h.top().sd;
                    sum += abs(x - tx) * w;
                    h.pop(); 
                    h.push({ -tx, ty + w });
                } else break;
            }
            v[i] += sum;
        }   

        sum = 0;
        while(!h.empty()){
            h.pop();
        }
        
        for(int i = r; i >= l; i--){
            h.push({-H[i], 1}); sum += H[i];
            while (!h.empty())
            {
                ll x = abs(h.top().fs), w = h.top().sd; 
                if(H[i] > x){
                    h.pop();
                    ll tx = -h.top().fs, ty = h.top().sd;
                    sum += abs(x - tx) * w;
                    h.pop(); 
                    h.push({ -tx, ty + w });
                } else break;
            }
            v[i] += sum;
        }   

        ll sol = Inf;
        for(int i = l; i <= r; i++){
            sol = min(sol, v[i] - H[i]);
        }

        return sol;
    };

   
    SegmentTree St(n);

    for(int i = 0; i < n; i++){
        //St.update(i, v[i]);
        //cerr << v[i] << " ";
    }

    vector <ll> ans(q);

    for(int i = 0; i < q; i++){
        //ans[i] = St.query(L[i], R[i]);
        ans[i] = F(L[i], R[i]);
    }

    return ans;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 4 ms 600 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 760 ms 896 KB Output is correct
11 Correct 2292 ms 1112 KB Output is correct
12 Correct 778 ms 880 KB Output is correct
13 Correct 2566 ms 888 KB Output is correct
14 Correct 685 ms 860 KB Output is correct
15 Correct 642 ms 892 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 5587 ms 2392 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 5587 ms 2392 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 760 ms 896 KB Output is correct
11 Correct 2292 ms 1112 KB Output is correct
12 Correct 778 ms 880 KB Output is correct
13 Correct 2566 ms 888 KB Output is correct
14 Correct 685 ms 860 KB Output is correct
15 Correct 642 ms 892 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Execution timed out 5587 ms 2392 KB Time limit exceeded
18 Halted 0 ms 0 KB -