玄关求调
查看原帖
玄关求调
566168
川寰boy楼主2024/11/25 20:21

90pts,WA on #2

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
using namespace std;

#define int long long
template <class T>
string toString(T x) { return to_string(x); }
string toString(const char *x) { return string(x); }
string toString(const string &x) { return x; }
template <class T>
string expand(const T &x) { return toString(x); }
template <class T, class... A>
string expand(const T &x, A... a) { return expand(x) + ", " + expand(a...); }
int read(){int type = 1, n = 0;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-'){type = -1;}ch = getchar();}while (ch >= '0' && ch <= '9'){n = (n << 1) + (n << 3) + (ch ^ 48),ch = getchar();}return n * type;}
void write(int n){if (n < 0){putchar('-'), n = -n;}if (n < 10){return putchar(n + '0'), void();}return write(n / 10), putchar(n % 10 + '0'), void();}
void wt(int n, bool o = 1){write(n);if (!o){putchar(' ');}else{putchar('\n');}}

#define debug(a...) cerr << "[" << #a << "] = " << expand(a) << '\n'
#define fileio(x) (freopen(x".in", "r", stdin), freopen(x".out", "w", stdout))
#define rd read()
#define ptc putchar('\n')
#define ls id << 1ll
#define rs id << 1ll | 1ll

const int N = 1e5 + 10;
const int MOD = 998244353;
const int INF = 0x7fffffff;
const int Fill = 0x3f3f3f3f;

map<int, int> mp;
int n, m, k;
int y[N];
struct Point
{
    int x, y, v;
    bool operator<(const Point &t) const
    {
        if (x == t.x) return y < t.y;
        return x < t.x;
    }
}point_[N];

struct node
{
    int l, r, max_;
}tr[N << 2];

void pushup(int id)
{
    tr[id].max_ = max(tr[ls].max_, tr[rs].max_);
}
void build(int id, int l, int r)
{
    tr[id] = {l, r, 0};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}
void mdf(int id, int pos, int v)
{
    if (tr[id].l == tr[id].r)
    {
        tr[id].max_ = max(tr[id].max_, v);
        return ;
    }
    int mid = tr[id].l + tr[id].r >> 1ll;
    if (pos <= mid) mdf(ls, pos, v);
    else mdf(rs, pos, v);
    pushup(id);
    return ;
}
int que(int id, int l, int r)
{
    if (l <= tr[id].l && tr[id].r <= r)
    {
        return tr[id].max_;
    }
    int mid = tr[id].l + tr[id].r >> 1ll;
    int max_ = 0;
    if (l <= mid)
    {
        max_ = max(max_, que(ls, l, r));
    }
    if (r > mid)
    {
        max_ = max(max_, que(rs, l, r));
    }
    return max_;
}

void solve()
{
    int i, j;
    n = rd, m = rd, k = rd;
    for (i = 1; i <= k; i++)
    {
        point_[i].x = rd, point_[i].y = rd, point_[i].v = rd;
        y[i] = point_[i].y;
    }
    sort(point_ + 1, point_ + k + 1);
    sort(y + 1, y + k + 1);
    int len = unique(y + 1, y + k + 1) - y;
    for (i = 1; i <= len; i++)
    {
        mp[y[i]] = i;
    }
    build(1, 1, k + 1);
    int ans = 0;
    for (i = 1; i <= k; i++)
    {
        
        int y_ = mp[point_[i].y];
        int v = que(1, 1, y_) + point_[i].v;
        mdf(1, y_, v);
        ans = max(v, ans);
    }
    wt(que(1, 1, k));
}

signed main()
{
    int T;
    int i, j;
    T = 1;
    while (T--)
    {
        
        solve();
    }
    return 0;
}
2024/11/25 20:21
加载中...