Submission #899906

#	Time	Username	Problem	Language	Result	Execution time	Memory
899906		beepbeepsheep	Homework (CEOI22_homework)	C++17	100 / 100	57 ms	39944 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
#define ll long long
#define ii pair<ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll inf=1e15;
const ll maxn=1e5+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

stack<ii> s;
ii solveMin(ii a, ii b){
	ll start=min(a.first,b.first);
	ll end=a.second+b.second+1;
	return {start,end};
}
ii solveMax(ii a, ii b){
	ll start=a.first+b.first+1;
	ll end=min(a.second,b.second);
	return {start,end};
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string str;
	ll cnt=0;
	cin>>str;
	for (int i=0;i<str.size();i++){
		if (str[i]=='('){
			if (str[i-1]=='x'){
				s.emplace(-1,-1); //max is -1, min is -2
			} else{
				s.emplace(-2,-2);
			}
		}
		if (str[i]=='?'){
			s.emplace(0,0);
			cnt++;
		}
		if (str[i]==')'){
			ii a=s.top();
			s.pop();
			ii b=s.top();
			s.pop();
			ii op=s.top();
			s.pop();
			assert(op.first<0);
			if (op.first==-1){
				s.emplace(solveMax(a,b));
			} else{
				s.emplace(solveMin(a,b));
			}
			//cerr<<s.top().first<<' '<<s.top().second<<endl;
		}
	}
	cout<<cnt-s.top().first-s.top().second;
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i=0;i<str.size();i++){
      |               ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34