fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define file "PARITY"
  5. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  6. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  7. #define nl "\n"
  8. #define ss " "
  9. #define mp make_pair
  10. //#define pb push_back
  11. #define pb emplace_back
  12. #define fi first
  13. #define se second
  14. #define sz(s) (int)s.size()
  15. #define all(s) (s).begin(), (s).end()
  16. #define ms(a,x) memset(a, x, sizeof (a))
  17. #define cn continue
  18. #define re exit(0)
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vll;
  25. typedef pair<int, int> pii;
  26. typedef pair<ll, ll> pll;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29.  
  30. const int mod=1e9+7;
  31. const int maxn=1e5+15;
  32. const int maxm=4*maxn+15;
  33. const ll inf=1e18;
  34.  
  35. void rf(){
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(nullptr); cout.tie(nullptr);
  38.     if(fopen(file".inp","r")){
  39.         freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  40.     }
  41. }
  42.  
  43. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  44. ll ran(ll l, ll r)
  45. {
  46.     return uniform_int_distribution<ll> (l, r)(rng);
  47. }
  48.  
  49. template<typename T> void add(T &x, const T &y)
  50. {
  51.     x+=y;
  52.     if(x>=mod) x-=mod;
  53.     if(x<0) x+=mod;
  54. }
  55.  
  56. template<typename T> bool maxi(T &a, T b)
  57. {
  58.     if(a>=b) return 0;
  59.     a=b; return 1;
  60. }
  61.  
  62. template<typename T> bool mini(T &a, T b)
  63. {
  64.     if(a<=b) return 0;
  65.     a=b; return 1;
  66. }
  67.  
  68. int n, m;
  69. struct queries{int op, l, r;} a[maxn];
  70. vi v;
  71. int par[maxn], sz[maxn];
  72. int fp(int u)
  73. {
  74.     if(u==par[u]) return u;
  75.     return par[u]=fp(par[u]);
  76. }
  77.  
  78. void unite(int u, int v)
  79. {
  80.     u=fp(u); v=fp(v);
  81.     if(u==v) return;
  82.     if(sz[u]<sz[v]) swap(u, v);
  83.     sz[u]+=sz[v]; par[v]=u;
  84.     return;
  85. }
  86.  
  87. bool lt(int u, int v)
  88. {
  89.     return fp(u)==fp(v);
  90. }
  91.  
  92. signed main()
  93. {
  94.     rf();
  95.     cin>>n>>m;
  96.     ff(i, 1, m)
  97.     {
  98.         string op; int l, r;
  99.         cin>>l>>r>>op;
  100.         if(op=="even") a[i]={0, l, r};
  101.         else a[i]={1, l, r};
  102.         v.pb(l); v.pb(r);
  103.     }
  104.     sort(all(v)); v.erase(unique(all(v)), v.end());
  105.     ff(i, 1, m)
  106.     {
  107.         int &l=a[i].l, &r=a[i].r;
  108.         l=upper_bound(all(v), l)-v.begin();
  109.         r=upper_bound(all(v), r)-v.begin();
  110.     }
  111.     int cur=sz(v)+1;
  112.     ff(i, 0, cur+cur) par[i]=i, sz[i]=1;
  113.     ff(i, 1, m)
  114.     {
  115.         int op, l, r;
  116.         op=a[i].op; l=a[i].l, r=a[i].r;
  117.         --l;
  118.         if(op==0)
  119.         {
  120.             if(lt(l, r+cur) || lt(l+cur, r)) return cout<<i-1, 0;
  121.             unite(l, r); unite(l+cur, r+cur);
  122.         }
  123.         else
  124.         {
  125.             if(lt(l, r) || lt(l+cur, r+cur)) return cout<<i-1, 0;
  126.             unite(l, r+cur); unite(l+cur, r);
  127.         }
  128.     }
  129.     cout<<m;
  130.     re;
  131. }
  132.  
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/F3iWmT
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!