Submission #1103435

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1103435	2024-10-21T02:12:54 Z	cccc	Nile (IOI24_nile)	C++17	Compilation error	0 ms	0 KB

nile

#include <bits/stdc++.h>
#define int long long
#define ld long double
#define f(i, a, b) for(int i = a; i <= b; i++)
#define fr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define in insert
#define arr(x) array <int, x>
#define vvec vector<vector<int>>
#define Keiiiii ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ___ 1000 * clock() / CLOCKS_PER_SEC

using namespace std;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e16;
int n, q, res;
int s[N], mnc[N], mnl[N], p[N], L[N], R[N], ans[N];
vector <pii> ee;
arr(3) a[N];
pii t[N];

void READ()
{
    cin >> n;
    f(i, 1, n) cin >> a[i][0] >> a[i][1] >> a[i][2];
    cin >> q;
    f(i, 1, q) cin >> t[i].fi, t[i].se = i;
}

struct ST
{
    int st[N * 4];
    ST() { memset(st, 0x3f, sizeof st); }
    void up(int i, int l, int r, int x, int y)
    {
        if(x > r || x < l) return;
        if(l == r) { st[i] = y; return; }
        int mid = (l + r) >> 1;
        up(i << 1, l, mid, x, y);
        up(i << 1 | 1, mid + 1, r, x, y);
        st[i] = min(st[i << 1], st[i << 1 | 1]);
    }

    int get(int i, int l, int r, int x, int y)
    {
        if(x > r || y < l) return inf;
        if(x <= l && r <= y) return st[i];
        int mid = (l + r) >> 1;
        return min(get(i << 1, l, mid, x, y), get(i << 1 | 1, mid + 1, r, x, y));
    }
} F[2], G[2];

int Find(int v) { return v == p[v] ? v : p[v] = Find(p[v]); }

int get(int l, int r)
{
    if(l == r) return a[l][1];
    int ans = s[r] - s[l - 1], ex = 0, len = r - l + 1;
    if(len % 2 == 1 && len > 2)
    {
        ex = F[(r - 1) % 2].get(1, 1, n, l, r - 1);
        ex = min(ex, G[r % 2].get(1, 1, n, l + 1, r - 1));
        ex = min({ex, a[l][1] - a[l][2], a[r][1] - a[r][2]});
    }
    return ans + ex;
}

void Us(int u, int v)
{
    u = Find(u); v = Find(v);
    if(u == v) return;
    res -= get(L[u], R[u]) + get(L[v], R[v]);
    L[u] = min(L[u], L[v]); R[u] = max(R[u], R[v]);
    res += get(L[u], R[u]); p[v] = u;
}

void SOLVE()
{
    vector <arr(3)> e;
    sort(a + 1, a + n + 1);
    sort(t + 1, t + q + 1);
    f(i, 1, n) p[i] = i, L[i] = R[i] = i;
    res = 0;
    f(i, 1, n)
    {
        res += a[i][1];
        s[i] = s[i - 1] + a[i][2];
        if(i % 2 == 0) F[0].up(1, 1, n, i, a[i][1] - a[i][2]);
        else F[1].up(1, 1, n, i, a[i][1] - a[i][2]);
    }
    f(i, 1, n - 1) e.pb({a[i + 1][0] - a[i][0], i, i + 1});
    f(i, 2, n - 1) ee.eb(a[i + 1][0] - a[i - 1][0], i);
    sort(e.begin(), e.end());

    int j = 0, j2 = 0;
    f(i, 1, q)
    {
        auto [d, id] = t[i];
        while(j2 < ee.size() && ee[j2].fi <= d)
        {
            int u = ee[j2].se;
            G[u % 2].up(1, 1, n, u, a[u][1] - a[u][2]);
        }

        while(j < n - 1 && e[j][0] <= d) Us(e[j][1], e[j][2]), j++;
        ans[id] = res;
    }
    f(i, 1, q) cout << ans[i] << "\n";
}

signed main()
{
    Keiiiii
    if(fopen("TASK.INP", "r"))
    {
        freopen("TASK.INP", "r", stdin);
        freopen("TASK.OUT", "w", stdout);
    }
    #define TASK "C"
    if(fopen(TASK ".INP", "r"))
    {
        freopen(TASK ".INP", "r", stdin);
        freopen(TASK ".OUT", "w", stdout);
    }
    int TEST = 1;
    while(TEST--)
    {
        READ();
        SOLVE();
    }
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

///    /\_/\
///   (= ._.)
///   / >  \>

Compilation message

nile.cpp:141:1: warning: multi-line comment [-Wcomment]
  141 | ///    /\_/\
      | ^
nile.cpp: In function 'void SOLVE()':
nile.cpp:105:18: 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]
  105 |         while(j2 < ee.size() && ee[j2].fi <= d)
      |               ~~~^~~~~~~~~~~
nile.cpp: In function 'int main()':
nile.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("TASK.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nile.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen("TASK.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
nile.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(TASK ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
nile.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(TASK ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cchuk5pT.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccSq2WvT.o:nile.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cchuk5pT.o: in function `main':
grader.cpp:(.text.startup+0x300): undefined reference to `calculate_costs(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status