Submission #1146231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146231		orzdraiduwu	Infinite Race (EGOI24_infiniterace2)	C++20	0 / 100	21 ms	2288 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;
  // if n == 2 we can just count how much times 
  /*

  no nvm, if k passes u... ok ok
  
  */

  // vector<int> k(n+1, 0);
  // map<int, bool> f;
  // for(int i = 0 ; i < q ; i++) {
  //   int x; cin >> x;
  //   int w = abs(x);
  //   if(x > 0) {
  //     if(!f[w]) k[w]++;
  //     f[w] = 0;
  //   }

  //   else {
  //     // if(f[w]) k[w]++;
  //     f[w] = 1;
  //   }
  // }

  // int r = 0;
  // for(int i = 0 ; i <= n ; i++) r = max(r, k[i]-1);
  // cout << r;
  int r = 0;
  vector<int> v(q);
  for(int i = 0 ; i < q ; i++) cin >> v[i];
  for(int i = 0 ; i < q-1 ;) {
    if(v[i] == -v[i+1]) i+=2;
    else if(v[i] > 0) r++;
    i++;
  }

  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: 0 / 29
• Subtask 2: 0 / 34
• Subtask 3: 0 / 22
• Subtask 4: 0 / 15