Submission #1148235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148235		ghammazhassan	Infinite Race (EGOI24_infiniterace2)	C++20	29 / 100	15 ms	14408 KiB

Main

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
#define endl "\n";
const int N=2e5+5;
const int M=1e9+7;
int n , q , x , y , p[N] , cnt[N] , ind[N];
vector<vector<int>>a(N);
vector<int>pr(N);
vector<int>e;
vector<int>l(N);
vector<pair<int,int>>li(N);
void solve()
{
	cin >> n >> q;

	vector<int>k(n+1);
	vector<bool>f(n+1);
	vector<int>p(n+1);
	int c=0;
	for (int i=0;i<q;i++){
		cin >> x;
		if (x>0){
			if (f[x]){
				k[x]++;
			}
			f[x]=1;
			p[x]=max(p[x],k[x]);
		}
		else{
			x*=-1;
			if (f[x]){
				f[x]=0;
			}
			p[x]=max(p[x],k[x]);
		}
	}
	for (int i:p)c+=i;
	// for (int i=1;i<n;i++){
	// 	c=max(c,mx[i]);
	// }
	cout << c << endl;
}
signed main()
{

    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed<<setprecision(9);
    int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
    	solve();
    }
}
// Fenwick Tree
// Sqrt Decomposition
// Segment Tree

• Subtask 1: 29 / 29
• Subtask 2: 0 / 34
• Subtask 3: 0 / 22
• Subtask 4: 0 / 15