제출 #1066190

#제출 시각UTC-0아이디문제언어결과실행 시간메모리
10661902024-08-19 16:12:06anango휴가 (IOI14_holiday)C++17
23 / 100
1897 ms15568 KiB
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define int long long
int INF = 1LL<<60;
//method:
//consider only going right, we'll try to compute the max obtainable with d days going to the right for each d
//now, let k be the number of cities we ever visit, and thus we get to actually see attractions of d-k cities
//we obviously visit the d-k cities with maximum attraction counts
//let visit(k,d) = max sum of visits for d with visiting the first k cities and actually opening d-k of them
//let opk[d] be the optimal number of cities to visit for d days
//note that opk[d+1]>=opk[d] (proved on paper)
//thus, for each d, there's a minimum k such that visit(k,d)<=visit(k+1,d), and from now we can use k+1 instead
//so binary search on this minimum k
//ok but we can't binary search this way round since that leads to too many insertions and erasures
//so we need to do a binary search on, for each k, the minimum d such that visit(k,d)<=visit(k+1,d)
//to do this, we need a data structure that can insert values, also query the sum of the maximum t values for any t
//this can be done with a segment tree of suffix sums with lazy propagation with coordinate compression
//since we know all the attraction values in advance
//keep a PBDS of what values are currently in the set
const int sz = 262144;
vector<int> revcoords;
class SegmentTree {
public:
vector<int> tree;
int n;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In member function 'long long int SegmentTree::get_sum_maximals(long long int)':
holiday.cpp:79:35: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::detail::tree_traits<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   79 |         if (current_indices.size()<k) {
      |             ~~~~~~~~~~~~~~~~~~~~~~^~
holiday.cpp: In function 'std::vector<long long int> solve_for_all_d(long long int, std::vector<long long int>)':
holiday.cpp:161:20: 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]
  161 |     for (int i=0; i<coords.size(); i++) {
      |                   ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...