oj.uz

Submission #533796

# Submission time Handle Problem Language Result Execution time Memory
533796 2022-03-07T09:35:10 Z PixelCat Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 12 ms 11084 KB 
/*       code by the cute PixelCat owo       */
/*   as cute as nacho neko (aka. my wife)!   */
// #pragma GCC
// optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
using uLL = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
#define LO(x) (x & (-x))

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

// #define MOD (int)(998244353)
#define MOD (int)(1e9 + 7)
#define INF (int)(9000000000000000000ll)  // 9e18
#define EPS (1e-6)

#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ans * b % mod;
        p /= 2;
        b = b * b % mod;
    }
    return ans;
}
int fpow(int b, int p) {
    return fpow(b, p, MOD);
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
// mt19937_64 rng(
//     chrono::steady_clock::now().time_since_epoch().count());

void insert(map<int,int> &a,int x,int y){
    if(a.count(x)) a[x]+=y;
    else a[x]=y;
}

// merge b into a
void merge(map<int,int> &a,map<int,int> &b){
    if(sz(a)<sz(b)) swap(a,b);
    for(auto &i:b){
        insert(a,i.F,i.S);
    }
}

void oao(map<int,int> &a,int x,int y){
    insert(a,x+1,y);
    auto it=prev(a.find(x+1));
    // debug(a,*it);
    while(y){
        int k=min(it->S,y);
        it->S-=k;
        y-=k;
        if(it->S==0){
            auto it1=it;
            it=prev(it);
            a.erase(it1);
        }else{
            it=prev(it);
        }
    }
    // debug(a);
}

const int MAXN=200020;

int a[MAXN];
int x[MAXN];
int c[MAXN];
map<int,int> dp[MAXN];
// int dd[MAXN][MAXN];

int32_t main() {
    NYA();
    // nyaacho >/////<
    // miku sama bless me >/////<
    int n; cin>>n;
    vector<int> al;
    For(i,1,n){
        cin>>a[i]>>x[i]>>c[i];
        al.eb(x[i]);
    }
    sort(all(al));
    al.erase(unique(all(al)),al.end());
    For(i,1,n){
        x[i]=upper_bound(all(al),x[i])-al.begin();
    }
    Forr(i,n,2){
        insert(dp[i],1,c[i]);
        oao(dp[i],x[i],c[i]);
        // cerr<<i<<"\t"<<dp[i]<<"\n";
        merge(dp[a[i]],dp[i]);
    }
    
    // int m=sz(al);
    // Forr(i,n,2){
    //     For(j,1,m) if(j!=x[i]) dd[i][j]+=c[i];
    //     Forr(j,m-1,1) chmin(dd[i][j],dd[i][j+1]);
    //     For(j,1,m) dd[a[i]][j]+=dd[i][j];
    //     cerr<<i<<"\t";
    //     For(j,1,m) cerr<<dd[i][j]<<" \n"[j==m];
    // }
    // For(j,1,m) if(j!=x[1]) dd[1][j]+=c[1];
    // Forr(j,m-1,1) chmin(dd[1][j],dd[1][j+1]);
    // cout<<dd[1][1]<<"\n";

    insert(dp[1],1,c[1]);
    oao(dp[1],x[1]+1,c[1]);
    insert(dp[1],1,0);
    cout<<dp[1][1]<<"\n";
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9724 KB Output is correct
5 Correct 11 ms 10956 KB Output is correct
6 Correct 10 ms 10444 KB Output is correct
7 Correct 9 ms 10192 KB Output is correct
8 Correct 12 ms 11084 KB Output is correct
9 Correct 9 ms 10444 KB Output is correct
10 Correct 8 ms 10188 KB Output is correct
11 Incorrect 7 ms 9932 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9724 KB Output is correct
5 Correct 11 ms 10956 KB Output is correct
6 Correct 10 ms 10444 KB Output is correct
7 Correct 9 ms 10192 KB Output is correct
8 Correct 12 ms 11084 KB Output is correct
9 Correct 9 ms 10444 KB Output is correct
10 Correct 8 ms 10188 KB Output is correct
11 Incorrect 7 ms 9932 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9724 KB Output is correct
5 Correct 11 ms 10956 KB Output is correct
6 Correct 10 ms 10444 KB Output is correct
7 Correct 9 ms 10192 KB Output is correct
8 Correct 12 ms 11084 KB Output is correct
9 Correct 9 ms 10444 KB Output is correct
10 Correct 8 ms 10188 KB Output is correct
11 Incorrect 7 ms 9932 KB Output isn't correct
12 Halted 0 ms 0 KB -