oj.uz

Submission #773286

# Submission time Handle Problem Language Result Execution time Memory
773286 2023-07-04T19:23:16 Z birthdaycake Fruits (NOI22_fruits) C++17
0 / 100
 1000 ms 35460 KB 
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
 
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#define endl '\n'
#define int long long
#define mod 1000000007
using namespace std;
 
 
int a[400001],c[400001],b[400001],mx[400001],cur[400001];
int seg[1000001];
int ans[400001];
int dp[3][400001];
int boo[400001];
int m,sz;
int N,Left,Right,Val;
vector<int>x;



void Update(int Pos, int V){
    int ind = N + Pos - 1;
    seg[ind] = V;
    while(ind /= 2) seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
}
void Spread(int ind){
    seg[ind * 2] = max(seg[ind * 2], seg[ind]);
    seg[ind * 2 + 1] = max(seg[ind * 2 + 1],seg[ind]);
}
void lazy(int l = 1, int r = N, int ind = 1){
    if(l != r) Spread(ind);
    if(l > Right or r < Left) return;
    if(l >= Left and r <= Right){
        seg[ind] = max(seg[ind], Val);
        return;
    }
    int mid = (l + r) / 2;
    lazy(l, mid, ind * 2);
    lazy(mid + 1, r, ind * 2 + 1);
}
int Query(int l = 1, int r = N, int ind = 1){
    if(l != r) Spread(ind);
    if(l > Right or r < Left) return -1e18;
    if(l >= Left and r <= Right) {
        //cout << l << ' ' << r << ' ' << seg[ind] << endl;
        return seg[ind];
    }
    int mid = (l + r) / 2;
    return max(Query(l, mid, ind * 2), Query(mid + 1, r, ind * 2 + 1));
}
signed main(){
    
    
    int n; cin >> n;
    N = exp2(ceil(log2(n)));
    b[0] = -1;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = max(a[i], b[i - 1]);
        if(a[i] > -1) boo[a[i]] = 1;
    }
    vector<int>x;
    int k = 0;
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
        if(!boo[i]) x.push_back(i);
    }
    for(int i = 1; i <= n; i++) {
        if(a[i] == -1) b[i] = max(b[i], x[k++]);
        b[i] = max(b[i - 1], b[i]);
    }
    int prev = 0;
    for(int i = 1; i <= n; i++){
        int xx = b[i];
        if(a[i] > -1 and a[i] >= xx){
            Left = a[i] - 1; Right = a[i] - 1;
            int val = Query();
            Left = a[i]; Right = n;
            Val = val + c[a[i]];
            //cout << a[i] << ' '<< Val << ' ' << val << endl;
            lazy();
        }else if(a[i] == -1){
            int boud = lower_bound(x.begin(), x.end(), xx) - x.begin();
            vector<pair<int,int>>u;
            for(int j = boud; j < x.size(); j++){
                Left = x[j] - 1; Right = x[j] - 1;
               // cout << Left << ' ' << Right << endl;
                int val = 0;
                if(Left != 0) val = Query();
               // cout << x[j] << ' ' << val << ' '<< val + c[x[j]] << endl;
                u.push_back({x[j], val + c[x[j]]});
            }
            for(int j = 0; j < u.size(); j++){
                Left = u[j].first; Right = n;
                Val = u[j].second;
                lazy();
            }
        }
        //cout << xx << endl;
        /*for(int j = xx; j <= n; j++){
            Left = j; Right = j;
            //cout << Query() << ' ' ;
        }
        
        cout << endl;*/
        Left = n; Right = n;
        ans[i] = Query();
        prev = xx - 1;
        for(int j = prev + 1; j < xx; j++){
            Update(j,-1e18);
        }
    }
    int mx = 0;
    for(int i = 1; i <= n; i++){
        mx = max(mx,ans[i]);
        cout << mx << ' ';
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:166:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |             for(int j = boud; j < x.size(); j++){
      |                               ~~^~~~~~~~~~
Main.cpp:174:30: 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]
  174 |             for(int j = 0; j < u.size(); j++){
      |                            ~~^~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 535 ms 516 KB Output is correct
3 Execution timed out 1076 ms 2512 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 13.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 35460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 42.0

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