Submission #710522

#	Time	Username	Problem	Language	Result	Execution time	Memory
710522		MinhAnhnd	Money (IZhO17_money)	C++14	100 / 100	1213 ms	103060 KiB

money

#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);
        auto ad = already_in.upper_bound(current-1);
        //cout<<current<<" "<<then<<endl;

        if(a==b || ad==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;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55