oj.uz

Submission #710522

# Submission time Handle Problem Language Result Execution time Memory
710522 2023-03-15T10:10:40 Z MinhAnhnd Money (IZhO17_money) C++14
100 / 100
 1213 ms 103060 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);
        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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55028 KB Output is correct
2 Correct 30 ms 55120 KB Output is correct
3 Correct 31 ms 55124 KB Output is correct
4 Correct 34 ms 54996 KB Output is correct
5 Correct 31 ms 55060 KB Output is correct
6 Correct 31 ms 54988 KB Output is correct
7 Correct 32 ms 55100 KB Output is correct
8 Correct 29 ms 55104 KB Output is correct
9 Correct 31 ms 54984 KB Output is correct
10 Correct 31 ms 55096 KB Output is correct
11 Correct 30 ms 55104 KB Output is correct
12 Correct 31 ms 55060 KB Output is correct
13 Correct 28 ms 54988 KB Output is correct
14 Correct 30 ms 55124 KB Output is correct
15 Correct 33 ms 54988 KB Output is correct
16 Correct 29 ms 55100 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55028 KB Output is correct
2 Correct 30 ms 55120 KB Output is correct
3 Correct 31 ms 55124 KB Output is correct
4 Correct 34 ms 54996 KB Output is correct
5 Correct 31 ms 55060 KB Output is correct
6 Correct 31 ms 54988 KB Output is correct
7 Correct 32 ms 55100 KB Output is correct
8 Correct 29 ms 55104 KB Output is correct
9 Correct 31 ms 54984 KB Output is correct
10 Correct 31 ms 55096 KB Output is correct
11 Correct 30 ms 55104 KB Output is correct
12 Correct 31 ms 55060 KB Output is correct
13 Correct 28 ms 54988 KB Output is correct
14 Correct 30 ms 55124 KB Output is correct
15 Correct 33 ms 54988 KB Output is correct
16 Correct 29 ms 55100 KB Output is correct
17 Correct 29 ms 54996 KB Output is correct
18 Correct 30 ms 55052 KB Output is correct
19 Correct 31 ms 55008 KB Output is correct
20 Correct 33 ms 55024 KB Output is correct
21 Correct 29 ms 55084 KB Output is correct
22 Correct 30 ms 55060 KB Output is correct
23 Correct 32 ms 55116 KB Output is correct
24 Correct 32 ms 54996 KB Output is correct
25 Correct 31 ms 55028 KB Output is correct
26 Correct 30 ms 54988 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55028 KB Output is correct
2 Correct 30 ms 55120 KB Output is correct
3 Correct 31 ms 55124 KB Output is correct
4 Correct 34 ms 54996 KB Output is correct
5 Correct 31 ms 55060 KB Output is correct
6 Correct 31 ms 54988 KB Output is correct
7 Correct 32 ms 55100 KB Output is correct
8 Correct 29 ms 55104 KB Output is correct
9 Correct 31 ms 54984 KB Output is correct
10 Correct 31 ms 55096 KB Output is correct
11 Correct 30 ms 55104 KB Output is correct
12 Correct 31 ms 55060 KB Output is correct
13 Correct 28 ms 54988 KB Output is correct
14 Correct 30 ms 55124 KB Output is correct
15 Correct 33 ms 54988 KB Output is correct
16 Correct 29 ms 55100 KB Output is correct
17 Correct 29 ms 54996 KB Output is correct
18 Correct 30 ms 55052 KB Output is correct
19 Correct 31 ms 55008 KB Output is correct
20 Correct 33 ms 55024 KB Output is correct
21 Correct 29 ms 55084 KB Output is correct
22 Correct 30 ms 55060 KB Output is correct
23 Correct 32 ms 55116 KB Output is correct
24 Correct 32 ms 54996 KB Output is correct
25 Correct 31 ms 55028 KB Output is correct
26 Correct 30 ms 54988 KB Output is correct
27 Correct 30 ms 54988 KB Output is correct
28 Correct 29 ms 55108 KB Output is correct
29 Correct 30 ms 55124 KB Output is correct
30 Correct 30 ms 55084 KB Output is correct
31 Correct 33 ms 54996 KB Output is correct
32 Correct 32 ms 55108 KB Output is correct
33 Correct 30 ms 54996 KB Output is correct
34 Correct 32 ms 55104 KB Output is correct
35 Correct 31 ms 54996 KB Output is correct
36 Correct 33 ms 55024 KB Output is correct
37 Correct 30 ms 55124 KB Output is correct
38 Correct 30 ms 55124 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55028 KB Output is correct
2 Correct 30 ms 55120 KB Output is correct
3 Correct 31 ms 55124 KB Output is correct
4 Correct 34 ms 54996 KB Output is correct
5 Correct 31 ms 55060 KB Output is correct
6 Correct 31 ms 54988 KB Output is correct
7 Correct 32 ms 55100 KB Output is correct
8 Correct 29 ms 55104 KB Output is correct
9 Correct 31 ms 54984 KB Output is correct
10 Correct 31 ms 55096 KB Output is correct
11 Correct 30 ms 55104 KB Output is correct
12 Correct 31 ms 55060 KB Output is correct
13 Correct 28 ms 54988 KB Output is correct
14 Correct 30 ms 55124 KB Output is correct
15 Correct 33 ms 54988 KB Output is correct
16 Correct 29 ms 55100 KB Output is correct
17 Correct 29 ms 54996 KB Output is correct
18 Correct 30 ms 55052 KB Output is correct
19 Correct 31 ms 55008 KB Output is correct
20 Correct 33 ms 55024 KB Output is correct
21 Correct 29 ms 55084 KB Output is correct
22 Correct 30 ms 55060 KB Output is correct
23 Correct 32 ms 55116 KB Output is correct
24 Correct 32 ms 54996 KB Output is correct
25 Correct 31 ms 55028 KB Output is correct
26 Correct 30 ms 54988 KB Output is correct
27 Correct 30 ms 54988 KB Output is correct
28 Correct 29 ms 55108 KB Output is correct
29 Correct 30 ms 55124 KB Output is correct
30 Correct 30 ms 55084 KB Output is correct
31 Correct 33 ms 54996 KB Output is correct
32 Correct 32 ms 55108 KB Output is correct
33 Correct 30 ms 54996 KB Output is correct
34 Correct 32 ms 55104 KB Output is correct
35 Correct 31 ms 54996 KB Output is correct
36 Correct 33 ms 55024 KB Output is correct
37 Correct 30 ms 55124 KB Output is correct
38 Correct 30 ms 55124 KB Output is correct
39 Correct 91 ms 55964 KB Output is correct
40 Correct 133 ms 55884 KB Output is correct
41 Correct 75 ms 55992 KB Output is correct
42 Correct 75 ms 55896 KB Output is correct
43 Correct 63 ms 56012 KB Output is correct
44 Correct 147 ms 55924 KB Output is correct
45 Correct 144 ms 56044 KB Output is correct
46 Correct 151 ms 56032 KB Output is correct
47 Correct 122 ms 55992 KB Output is correct
48 Correct 137 ms 56032 KB Output is correct
49 Correct 457 ms 74420 KB Output is correct
50 Correct 450 ms 74576 KB Output is correct
51 Correct 475 ms 74404 KB Output is correct
52 Correct 497 ms 74716 KB Output is correct
53 Correct 520 ms 74604 KB Output is correct
54 Correct 522 ms 74432 KB Output is correct
55 Correct 1130 ms 103060 KB Output is correct
56 Correct 1044 ms 102988 KB Output is correct
57 Correct 1063 ms 103052 KB Output is correct
58 Correct 1060 ms 103012 KB Output is correct
59 Correct 1088 ms 102964 KB Output is correct
60 Correct 1089 ms 102984 KB Output is correct
61 Correct 1040 ms 102988 KB Output is correct
62 Correct 1213 ms 103052 KB Output is correct