Submission #666191

#	Time	Username	Problem	Language	Result	Execution time	Memory
666191		nolimiya	Homework (CEOI22_homework)	C++14	100 / 100	315 ms	374692 KiB

Main

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//**gray sety orz**
using namespace std;
#define pi pair<int , int>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 2e6 + 5;
const long long mod = 1e9 + 7;
const int SQ = 12;
typedef long long ll;
int l,r,mid;
int n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
int darage[maxm] , ss , mm;
queue<int> q;
vector<int> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm*SQ] , gos[maxm];
int pedaret[maxm*SQ];
ll get_par(ll v){
    if (pedaret[v]==v) return v;
    return pedaret[v] = get_par(pedaret[v]);
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
set<ll> st,ts;
int rp[maxm] , pr[maxm];
ll dp[maxm*SQ];
pi w[maxm];
int rw[400][400];
int dage[maxm*SQ];
map<ll,ll> mp,pm,f;
priority_queue<pi> lowq;
priority_queue<int, vector<int>, greater<int> > upq;
void solve(int v, int u , int w);
void dfs(int v){
    if (!g[v].size()){ pedaret[v] = darage[v] = sath[v] = 1;
        return;
    }
    auto u=g[v][0], w=g[v][1];
    dfs(u) , dfs(w);
    solve(v,u,w);
    return;
}
void solve(int v,int u, int w){
	sath[v] = sath[u]+sath[w];
    if (vis[v]){
        l = sath[u]-darage[u]+1 , r = sath[u]-(pedaret[u]-1);
        pedaret[u] = l , darage[u] = r;
        l = sath[w]-darage[w]+1 , r = sath[w]-(pedaret[w]-1);
        pedaret[w] = l , darage[w] = r;
    }
    if (vis[v]) swap(u,w);
    darage[v] = sath[v]-(sath[u]-darage[u]+sath[w]-darage[w]+1);
    pedaret[v] = min(pedaret[u],pedaret[w]);
    if (vis[v]) l=sath[v]-darage[v]+1 , r=sath[v]-(pedaret[v]-1) , pedaret[v]=l , darage[v]=r;
    return;
}
vector<int> vec;
void prep(){
	for (int i=1; i<=n; i++) vis[i] = darage[i] = 0;
}
void solve(ll x){
	for (int i=0; i<31; i++){
		if (x&(1<<i)) dp[i]++;
	}
	return ;
}
bool val(int x){
	//cout<<x<<" ";
	if (x>n/2) return 0;
	for (int i=1; i<=x; i++){
		//cout<<x<<" "<<pedaret[n-x+i]<<" "<<pedaret[i]<<endl;
		if (pedaret[n-x+i]-pedaret[i]<m) return 0;
	}
	return 1;
}
string k[maxm],t[maxm];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s;
    cin >>s;
    vector<int> vec;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='m'){
            if(vec.size()) g[vec.back()].push_back(m);
            vec.push_back(m);
            vis[m]=(s[i+2]=='x'?1:0);
            m++;
            i+=3;
        }
        else if(s[i]==')') vec.pop_back();
        else if(s[i]=='?') g[vec.back()].push_back(m),m++;
    }
    dfs(0) , cout<<darage[0]-pedaret[0]+1<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'void prep()':
Main.cpp:67:46: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   67 |  for (int i=1; i<=n; i++) vis[i] = darage[i] = 0;
      |                                    ~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~

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