oj.uz

Submission #344693

# Submission time Handle Problem Language Result Execution time Memory
344693 2021-01-06T08:05:32 Z I_use_Brute_force Segments (IZhO18_segments) C++14
0 / 100
 5000 ms 5496 KB 
#include <bits/stdc++.h>	
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define ld long double
#define pii pair <int, int>
#define sz(a) (int)(a.size()) 
#define resize(v) v.resize(unique(all(v)) - v.begin()); 
#define all(a) a.begin(), a.end()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)

// random_device rd; mt19937 g(rd());    
                                        	
using namespace std;
using namespace __gnu_pbds;
 
void Fast_Read_Out()
{
    ios_base::sync_with_stdio(0);
    cin.tie(), cout.tie();
}
 
void Random()
{
    unsigned int seed;                                                                        
    asm("rdtsc" : "=A" (seed));
    srand(seed);        
}
 
unsigned int Time()
{
     unsigned int time = clock() / 1000.00;                           
     return time;
}

template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; 
 
const int mod = (int)1e9 + 7;
const int N = (int)1e5 + 1;

map <int, pair <int, int> > d;
int used[N];
int n, t;

int main ()
{
	#ifdef JUDGE
		freopen("input.txt", "r", stdin);
	#endif		
	Fast_Read_Out();
	Random();
	cin >> n >> t;
	int lastans = 0;
	for(int i = 1; i <= n; i++)
	{
		int type;
		cin >> type;
		int a, b, k;
		if(type == 1)
		{            
			cin >> a >> b;
			int l = (a ^ (t * lastans));
			int r = (b ^ (t * lastans));
			if(l > r) swap(l, r);
			for(int j = 1; j <= n; j++) 
			{
				if(!used[j])
				{
					d[j] = mp(l, r);
					used[j] = 1;
					break;
				}
			}
		}
		else if(type == 2)
		{
			int it;
			cin >> it;
			used[it] = 0;
			d[it] = mp(0, 0);
		}
		else
		{
			cin >> a >> b >> k;
			int l = (a ^ (t * lastans));
			int r = (b ^ (t * lastans));
			if(l > r) swap(l, r);
			k--;
			if(r - l < k) 
			{
				lastans = 0;
				cout << lastans << '\n';
				continue;
			}
			lastans = 0;
			for(auto to : d)
			{
				if(to.S.S - to.S.F < k) continue;
				if(to.S.F <= l && r <= to.S.S) 
				{
					lastans++;
					continue;
				}
				if(l < to.S.F && to.S.F + k <= r && to.S.F + k <= to.S.S) 
				{
					lastans++;
					continue;
				}
				if(r > to.S.S && to.S.S - k >= l && to.S.S - k >= to.S.F)
				{
					lastans++;
					continue;
				}
			}
			cout << lastans << '\n';
		}
	}	
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 30 ms 620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5057 ms 5496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5023 ms 3492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5058 ms 3472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 30 ms 620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 30 ms 620 KB Output isn't correct
4 Halted 0 ms 0 KB -