Submission #366376

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
366376	2021-02-14T06:00:03 Z	strawberry2005	Po (COCI21_po)	C++17	70 / 70	13 ms	876 KB

Main

#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout.precision(20);
const int mod = 1e9+7;
using namespace std;
#define ll long long
#define deb(x) cout<<#x<<": "<<x<<endl

int iceil(int a, int b) {
  return (a + b - 1) / b;
}


vector<int> segtree;

void build_segtree(int start_node,int ar[],int l,int r){
	if(l==r){
		segtree[start_node]=ar[l];
	}
	else{
		int mid=(l+r)/2;
		build_segtree(2*start_node,ar,l,mid);
		build_segtree(2*start_node+1,ar,mid+1,r);
		segtree[start_node]=segtree[2*start_node]+segtree[2*start_node+1];
	}
}
int sum_query_ans=0;
int sum_query(int node,int l,int r,int ql,int qr){
	if(qr<l||r<ql) return(0);
	if(l>=ql&&r<=qr) return(segtree[node]);
	int mid=(l+r)/2;
	sum_query_ans=sum_query(node*2,l,mid,ql,qr)+sum_query(node*2+1,mid+1,r,ql,qr);
	return(sum_query_ans);
}
int calculate_node(int node,int index,int start,int end){
	if((start<index&&end<index)||(start>index&&end>index)) return(1);
	if(start==end&&start==index) return(node);
	int mid=(start+end)/2;
	node=max(calculate_node(node*2,index,start,mid),calculate_node(node*2+1,index,mid+1,end));

	return(node);
}

void upd_segtree(int node,int ar[],int index,int change,int start,int end){
	if(start==end){
		ar[index]+=change;
		segtree[node]+=change;
	}
	else{
		int mid=(start+end)/2;
		if(start<=index&&index<=mid) upd_segtree(2*node,ar,index,change,start,mid);
		else upd_segtree(2*node+1,ar,index,change,mid+1,end);
		segtree[node]=segtree[node*2]+segtree[node*2+1];
	}
}

signed main(){
	//Always resize the segtree vector to 4*n when using a segtree!!!
    IOS;

    int n;
    cin>>n;
    int ar[n];
    for(int i=0;i<n;i++) cin>>ar[i];
    stack<int> st;
	st.push(0);
	int count=0;
	for(int i=0;i<n;i++){
		while(!st.empty()&&st.top()>ar[i]) st.pop();
		
		if(st.top()==ar[i]) continue;
		st.push(ar[i]);
		count++;
	}
	cout<<count<<endl;

	

    return(0);
}

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	5 ms	492 KB	Output is correct
5	Correct	9 ms	620 KB	Output is correct
6	Correct	13 ms	876 KB	Output is correct
7	Correct	12 ms	748 KB	Output is correct