oj.uz

Submission #861967

# Submission time Handle Problem Language Result Execution time Memory
861967 2023-10-17T09:38:20 Z 12345678 Salesman (IOI09_salesman) C++17
60 / 100
 560 ms 39500 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;
int n, u, d, s, x, y, z;
vector<pair<int, int>> t[nx];

struct segtree
{
    int d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=-2e9);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=max(d[i], vl));
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (r<ql||qr<l) return INT_MIN;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} up, dn;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>u>>d>>s;
    for (int i=0; i<n; i++) cin>>x>>y>>z, t[x].push_back({y, z});
    up.build(1, nx-1, 1); dn.build(1, nx-1, 1);
    up.update(1, nx-1, 1, s, -s*u); dn.update(1, nx-1, 1, s, s*d);
    for (int i=1; i<nx; i++)
    {
        sort(t[i].begin(), t[i].end());
        vector<int> cal(t[i].size()), tmp(t[i].size()), rtmp(t[i].size());
        for (int j=0; j<t[i].size(); j++)
        {
            int y=t[i][j].first, z=t[i][j].second;
            int qup=up.query(1, nx-1, 1, y, nx-1);
            int qdn=dn.query(1, nx-1, 1, 1, y);
            cal[j]=tmp[j]=rtmp[j]=max(qup+y*u, qdn-y*d)+z;
        }
        for (int j=1; j<t[i].size(); j++) tmp[j]=max(tmp[j], (t[i][j].first-t[i][j-1].first)*d+t[i][j].second);
        for (int j=(int)t[i].size()-2; j>=0; j--) rtmp[j]=max(rtmp[j], (t[i][j+1].first-t[i][j].first)*u+t[i][j].second);
        for (int j=0; j<t[i].size(); j++) 
        {
            int y=t[i][j].first;
            up.update(1, nx-1, 1, y, max(tmp[j], rtmp[j])-y*u);
            dn.update(1, nx-1, 1, y, max(tmp[j], rtmp[j])+y*d);
        }
    }
    cout<<max(up.query(1, nx-1, 1, s, nx-1)+s*u, dn.query(1, nx-1, 1, 1, s)-s*d);
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:49:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int j=0; j<t[i].size(); j++)
      |                       ~^~~~~~~~~~~~
salesman.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j=1; j<t[i].size(); j++) tmp[j]=max(tmp[j], (t[i][j].first-t[i][j-1].first)*d+t[i][j].second);
      |                       ~^~~~~~~~~~~~
salesman.cpp:58:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int j=0; j<t[i].size(); j++)
      |                       ~^~~~~~~~~~~~

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23644 KB Output is correct
2 Correct 8 ms 23644 KB Output is correct
3 Correct 8 ms 23644 KB Output is correct
4 Correct 9 ms 23640 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 24 ms 24156 KB Output is correct
7 Correct 63 ms 25144 KB Output is correct
8 Correct 102 ms 26716 KB Output is correct
9 Correct 151 ms 28424 KB Output is correct
10 Correct 251 ms 33108 KB Output is correct
11 Correct 327 ms 32936 KB Output is correct
12 Correct 416 ms 36244 KB Output is correct
13 Correct 429 ms 36180 KB Output is correct
14 Correct 505 ms 39388 KB Output is correct
15 Correct 414 ms 39380 KB Output is correct
16 Correct 560 ms 39500 KB Output is correct
17 Incorrect 7 ms 23644 KB Output isn't correct
18 Incorrect 10 ms 23760 KB Output isn't correct
19 Incorrect 8 ms 23644 KB Output isn't correct
20 Incorrect 9 ms 23644 KB Output isn't correct
21 Incorrect 9 ms 23796 KB Output isn't correct
22 Incorrect 12 ms 23644 KB Output isn't correct
23 Incorrect 10 ms 23640 KB Output isn't correct
24 Incorrect 13 ms 23644 KB Output isn't correct
25 Incorrect 87 ms 24916 KB Output isn't correct
26 Incorrect 135 ms 26172 KB Output isn't correct
27 Incorrect 220 ms 27972 KB Output isn't correct
28 Incorrect 250 ms 27972 KB Output isn't correct
29 Incorrect 314 ms 28496 KB Output isn't correct
30 Incorrect 333 ms 29736 KB Output isn't correct