| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 710514 |
2023-03-15T09:59:22 Z |
MinhAnhnd |
Money (IZhO17_money) |
C++14 |
|
30 ms |
55116 KB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//long R,n,m,p,totalsum = 0;
#define limit 1000001
#define Nmax limit
using namespace std;
/*
vector<int> graph[limit];
int timer = 0, tin[limit], euler_tour[limit];
//int segtree[800000]; // Segment tree for RMQ
void dfs(int node = 0, int parent = -1) {
tin[node] = timer; // The time when we first visit a node
euler_tour[timer++] = node;
for (int i : graph[node]) {
if (i != parent) {
dfs(i, node);
euler_tour[timer++] = node;
}
}
}
long k = 0;
long tmax[limit*2] ={};
long tmin[limit*2] ={};
#include <bits/stdc++.h>*/
typedef long long ll;
using namespace std;
struct Line {
bool type;
long double x;
ll m, c;
};
bool operator<(Line l1, Line l2) {
if (l1.type || l2.type) return l1.x < l2.x;
return l1.m > l2.m;
}
set<Line> cht[1];
long cht_pointer = 0;
//ll h[100001], w[100001], tot = 0, dp[100001];
bool has_prev(set<Line>::iterator it) { return it != cht[cht_pointer].begin(); }
bool has_next(set<Line>::iterator it) {
return it != cht[cht_pointer].end() && next(it) != cht[cht_pointer].end();
}
long double intersect(set<Line>::iterator l1, set<Line>::iterator l2) {
return (long double)(l1->c - l2->c) / (l2->m - l1->m);
}
void calc_x(set<Line>::iterator it) {
if (has_prev(it)) {
Line l = *it;
l.x = intersect(prev(it), it);
cht[cht_pointer].insert(cht[cht_pointer].erase(it), l);
}
}
bool bad(set<Line>::iterator it) {
if (has_next(it) && next(it)->c <= it->c) return true;
return (has_prev(it) && has_next(it) &&
intersect(prev(it), next(it)) <= intersect(prev(it), it));
}
void add_line(ll m, ll c) {
set<Line>::iterator it;
it = cht[cht_pointer].lower_bound({0, 0, m, c});
if (it != cht[cht_pointer].end() && it->m == m) {
if (it->c <= c) return;
cht[cht_pointer].erase(it);
}
it = cht[cht_pointer].insert({0, 0, m, c}).first;
if (bad(it)) cht[cht_pointer].erase(it);
else {
while (has_prev(it) && bad(prev(it))) cht[cht_pointer].erase(prev(it));
while (has_next(it) && bad(next(it))) cht[cht_pointer].erase(next(it));
if (has_next(it)) calc_x(next(it));
calc_x(it);
}
}
ll query(ll h) {
Line l = *prev(cht[cht_pointer].upper_bound({1, (long double)h, 0, 0}));
return l.m * h + l.c;
}
/*long long Y,N, parent[limit] = {}, weight[limit] = {}, dp[limit] ={}, incon[limit] = {};
long long distance_[limit] = {};
long long num_child[limit] ={};
vector<long> children[limit];
stack<long> tovisit;
bool visited[limit] = {};
long moveit(ll current){
if (!children[current].empty()) tovisit.push(current);
long long sum = 0;
for (auto i: children[current]){
//cout<<i<<"checker";
distance_[i] = distance_[current] + weight[i];
sum += moveit(i);
//cout<<sum<<"checker";
}
if (children[current].empty()) return (long long) 1;
num_child[current] = (long long) sum;
return sum;
}*/
#define T pair<long,long>
struct node{
long long A,L;
};
bool ss(node a,node b){
//if (a.L==b.L) return a.A<b.A;
return (a.L+a.A)<(b.L+b.A);
}
vector<long> adj[Nmax];
vector<long> children[Nmax];
vector<long> iter;
long parent[Nmax];
void dfs(int node,int par){
parent[node] = par;
for (auto togo: adj[node])if(togo!=par){
children[node].push_back(togo);
dfs(togo,node);
}
iter.push_back(node);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
long N, ans = 0;
set<long> already_in;
long A[limit] = {};
A[0] = LONG_MAX;
long currentL = 0, currentR = 0, current,then;
cin>>N;
for(long i = 1;i<=N;i++){
cin>>current;
A[i] = current;
if(A[i]<A[i-1]){
ans++;
for (long j = currentL;j<=currentR;j++){
if(A[j]!=LONG_MAX){
already_in.insert(A[j]);
}
}
currentL = i;
currentR = i;
then = A[i];
continue;
}
auto a = already_in.upper_bound(current);
auto b = already_in.upper_bound(then);
//cout<<current<<" "<<then<<endl;
if(a==b){
currentR = i;
}else{
ans++;
for (long j = currentL;j<=currentR;j++){
if(A[j]!=LONG_MAX){
already_in.insert(A[j]);
}
}
currentL = i;
currentR = i;
then = A[i];
continue;
}
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
55092 KB |
Output is correct |
| 2 |
Correct |
29 ms |
54996 KB |
Output is correct |
| 3 |
Correct |
30 ms |
54996 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
55116 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
55092 KB |
Output is correct |
| 2 |
Correct |
29 ms |
54996 KB |
Output is correct |
| 3 |
Correct |
30 ms |
54996 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
55116 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
55092 KB |
Output is correct |
| 2 |
Correct |
29 ms |
54996 KB |
Output is correct |
| 3 |
Correct |
30 ms |
54996 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
55116 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
55092 KB |
Output is correct |
| 2 |
Correct |
29 ms |
54996 KB |
Output is correct |
| 3 |
Correct |
30 ms |
54996 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
55116 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
