I am trying to solve 1284D - New Year and Conference I used a randomized approach involving hashes. I assigned random numbers to each lecture and then calculated for each lecture the xor of numbers assigned to lectures it intersects with. Now I checked that every lecture has same hashes in first location (a) and second location (b)
Take a look at my submission : 68617652 I am getting WA on test 6.
Any advice would be greatly appreciated.
Thanks in advance :)
//i am getting timeout on test case 6 //plzz help
include <bits/stdc++.h>
using namespace std;
bool overlap(int x, int y, int u,int v) { if(max(x,u) <= min(y,v)) return true; return false; }
int main(void) { int n; cin >> n; int sa[100000],ea[100000],sb[100000],eb[100000]; for(int i = 0; i < n; i++) { cin >> sa[i] >>ea[i] >> sb[i] >> eb[i]; for(int j = 0; j <= i-1; j++) { if(overlap(sa[i],ea[i],sa[j],ea[j]) ^ overlap(sb[i],eb[i],sb[j],eb[j])) { cout << "NO" <<endl; return 0; } } }
}