Submission #1146300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146300		orzdraiduwu	Infinite Race (EGOI24_infiniterace2)	C++20	100 / 100	101 ms	9800 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
void dbg(vector<int> &v) { for(int k: v) cout << k << " "; }
void dbg(map<int, int> &v) { for(auto [a, b]: v) cout << a << " " << b << '\n'; }
void dbg(set<int> &v) { for(int k: v) cout << k << " "; }
 
struct DSU {
  vector<int> par, sz;
  DSU(int n) {
    par.resize(n+1);
    sz.resize(n+1, 1);
    for(int i = 0 ; i <= n ; i++) par[i] = i;
  }
 
  int pfind(int v) {
    if(v == par[v]) return v;
    else return par[v] = pfind(par[v]);
  }
 
  void sunion(int a, int b) {
    a = pfind(a);
    b = pfind(b);
    if(a == b) return;
    if(sz[a] > sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
  }
};

const int MOD = 1e9 + 7;
using pr = array<int, 3>;
const int MX = 2e5 + 1;

void solve() {
  int n, q; cin >> n >> q;
  set<int> g;
  int r = 0;
  int f=0;
  for(int i = 0 ; i < q ; i++) {
    int x; cin >> x;
    if(x > 0) {
      if(g.contains(-x)) g.erase(-x);
      else if(g.contains(x)) {
        g.clear();
        r++;
      }

      g.insert(x);
    }

    else {
      // g.erase(-x);
      g.insert(x);
    }
  }

  cout << r;
}

signed main() {
  // int t; cin >> t;
  int t = 1;
  while(t--) solve();
}
 
// think greedy first, Div2AB usually are some sort of greedy, super simple usually
// C on Div2 or E on Div3/4 require more thinking but still not too hard
// for later problems, think about data structures like segment tree and ordered set
// do smth instead of nothing and stay organized
// WRITE STUFF DOWN
// DON'T GET STUCK ON ONE APPROACH

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