oj.uz

Submission #1112768

# Submission time Handle Problem Language Result Execution time Memory
1112768 2024-11-14T19:38:08 Z FIFI_cpp Nile (IOI24_nile) C++17
23 / 100
 114 ms 35608 KB 
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>

#define all(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ppi pair<int,pair<int,int>>
//#define int long long
#define ll long long

using namespace std;
//    /\_/\
//   (= ._.)
//   / >  \>
// encouraging cat
const int INF = 10000000000000000;
const int mod = 1000000007;
//const int mod = 998244353;
const int MAXN = 200005;
//ifstream fin('xor.in');
//ofstream fout('xor.out');
ll curr_res = 0;

struct Index {
    ll a,b,w;
};
struct Node {
    ll parent, min_value, min_index, size, sb, l, r;
};
vector<Index> vals;
vector<Node> info;
vector<pair<ll,ll>> e;
bool cmp(const Index &x, const Index &y) { return x.w < y.w; }
ll find_parent(ll x)
{
    if (x == info[x].parent)
    {
        return x;
    }
    return info[x].parent = find_parent(info[x].parent);
}
void remove(Node x, int ix)
{
    if (x.size == 1)
    {
        curr_res -= vals[ix].a;
    }
    else if (x.size % 2 == 0)
    {
        curr_res -= x.sb;
    }
    else
    {
        curr_res -= x.sb + min(x.min_value, min(vals[x.l].a - vals[x.l].b, vals[x.r].a - vals[x.r].b));
    }
}
void add(Node x)
{
    if (x.size % 2 == 0)
    {
        curr_res += x.sb;
    }
    else
    {
        curr_res += x.sb + min(x.min_value, min(vals[x.l].a - vals[x.l].b, vals[x.r].a - vals[x.r].b));
    }
}
pair<Node, Node> merge(Node x,Node y, ll ix, ll iy)
{
    y.parent = ix;
    x.size += y.size;
    if (y.min_value < x.min_value)
    {
        x.min_value = y.min_value;
        x.min_index = y.min_index;
    }
    x.sb += y.sb;
    x.l = min(x.l, y.l);
    x.r = max(x.r,y.r);
    return {x,y};
}
void onion (ll x, ll y)
{
    x = find_parent(x);
    y = find_parent(y);
    if (x == y)
        return;
    remove(info[x], x);
    remove(info[y], y);
    if (info[y].size > info[x].size)
    {
        swap(x,y);
    }
    pair<Node, Node> m = merge(info[x], info[y], x, y);
    info[x] = m.first;
    info[y] = m.second;
    add(info[x]);
}
Node set_best(Node x, int index)
{
    if (x.size % 2)
        curr_res -= x.sb + min(x.min_value, min(vals[x.l].a - vals[x.l].b, vals[x.r].a - vals[x.r].b));
    if (vals[index].a - vals[index].b < x.min_value)
    {
        x.min_value = vals[index].a - vals[index].b;
        x.min_index = index;
    }
    if (x.size % 2)
        curr_res += x.sb + min(x.min_value, min(vals[x.l].a - vals[x.l].b, vals[x.r].a - vals[x.r].b));
    return x;
}
std::vector<ll> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
    ll n = A.size();
    info.resize(n);
    vals.resize(n);
    for (ll i = 0;i < n;i++)
    {
        vals[i].a = A[i];
        vals[i].b = B[i];
        vals[i].w = W[i];
    }
    sort(all(vals), cmp);
    for (ll i = 0;i < n;i++)
    {
        info[i].l = i;
        info[i].r = i;
        info[i].parent = i;
        info[i].min_index = i;
        info[i].min_value = INF;
        info[i].sb = vals[i].b;
        info[i].size = 1;
        curr_res += vals[i].a;
    }
    ll q = E.size();
    e.resize(q);
    for (ll i = 0;i < q;i++)
    {
        e[i].first = E[i];
        e[i].second = i;
    }
    sort(all(e));
    vector<pair<ll,ll>> diff;
    for (ll i = 0;i < n - 1;i++)
    {
        diff.push_back({vals[i + 1].w - (ll)vals[i].w, -i - 1});
        if (i < n - 2)
        {
            diff.pb({vals[i + 2].w - (ll)vals[i].w, i + 1});
        }
    }
    sort(all(diff));
    vector<ll> res(q);
    ll e_index = 0;
    info[0].min_value = vals[0].a - vals[0].b;
    info[n - 1].min_value = vals[n - 1].a - vals[n - 1].b;
    for (ll i = 0;i < diff.size();i++)
    {
        if (diff[i].first <= e[e_index].first)
        {
            if (diff[i].second < 0)
            {
                int mergei = diff[i].second * -1 - 1;
                ll a = mergei;
                ll b = mergei + 1;
                onion(a,b);
            }
            else
            {
                diff[i].second--;
                int nd = find_parent(diff[i].second + 1);
                info[nd] = set_best(info[nd], diff[i].second + 1);
            }
        }
        else
        {
            res[e[e_index].second] = curr_res;
            e_index++;
            i--;
        }
        
    }
    for (; e_index < q;e_index++)
    {
        res[e[e_index].second] = curr_res;
    }
    return res;
}

Compilation message

nile.cpp:33:1: warning: multi-line comment [-Wcomment]
   33 | //    /\_/\
      | ^
nile.cpp:37:17: warning: overflow in conversion from 'long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
   37 | const int INF = 10000000000000000;
      |                 ^~~~~~~~~~~~~~~~~
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:178:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for (ll i = 0;i < diff.size();i++)
      |                   ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 708 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 17336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15812 KB Output is correct
2 Correct 58 ms 16200 KB Output is correct
3 Correct 61 ms 16056 KB Output is correct
4 Correct 63 ms 16184 KB Output is correct
5 Correct 63 ms 16056 KB Output is correct
6 Correct 69 ms 16056 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 708 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Incorrect 2 ms 592 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 708 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Incorrect 49 ms 17336 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15812 KB Output is correct
2 Correct 58 ms 16200 KB Output is correct
3 Correct 61 ms 16056 KB Output is correct
4 Correct 63 ms 16184 KB Output is correct
5 Correct 63 ms 16056 KB Output is correct
6 Correct 69 ms 16056 KB Output is correct
7 Runtime error 114 ms 35608 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -