oj.uz

Submission #62049

# Submission time Handle Problem Language Result Execution time Memory
62049 2018-07-27T09:48:08 Z Mahmoud_Adel Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 3000 ms 5224 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update


#define f first
#define s second
#define pb push_back
#define mp make_pair
#define clr(dp,i) memset(dp,i,sizeof(dp))
#define opt     ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define inf 0x3f3f3f3f
using namespace std;
using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_t_tag,
//t_order_statistics_node_update> oset;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const long long mod = 1e9+7;
const ld pi = 3.14159265358979323846264338327950288;
//==================================================
const int N = 2e5+1;
ll n, k, q, a[N], b[N], sz[4*N][2];
ll t[4*N][2], mn[4*N][2], mx[4*N][2];
void build(int l, int r, int id)
{
	if(l == r)
	{
		sz[id][0] = a[l];
		sz[id][1] = b[l];
		mn[id][0] = a[l], mx[id][0] = a[l];
		mn[id][1] = b[l], mx[id][1] = b[l];
		return ;
	}
	int mid = (l+r)/2;
	build(l, mid, id*2);
	build(mid+1, r, id*2+1);
	mn[id][0] = min(mn[id*2][0], mn[id*2+1][0]);
	mn[id][1] = min(mn[id*2][1], mn[id*2+1][1]);
	mx[id][0] = max(mx[id*2][0], mx[id*2+1][0]);
	mx[id][1] = max(mx[id*2][1], mx[id*2+1][1]);
	sz[id][0] = sz[id*2][0] + sz[id*2+1][0];
	sz[id][1] = sz[id*2][1] + sz[id*2+1][1];
}
void query(int l, int r, int id, ll x)
{
	if(t[id][0])
	{
		t[id][0] = 0;
		swap(mn[id][0], mn[id][1]);
		swap(mx[id][0], mx[id][1]);
		swap(sz[id][0], sz[id][1]);
		if(l != r)
		t[id*2][0] ^= 1, t[id*2+1][0] ^= 1;
	}
	if(mn[id][0] > x)
	return;
	if(mx[id][0] <= x)
	{
		swap(mx[id][0], mx[id][1]);
		swap(mn[id][0], mn[id][1]);
		swap(sz[id][0], sz[id][1]);
		if(l != r)
		t[id*2][0] ^= 1, t[id*2+1][0] ^= 1;
		return ;
	}
	int mid = (l+r)>>1;
	query(l, mid, id*2, x);
	query(mid+1, r, id*2+1, x);
	mn[id][0] = min(mn[id*2][0], mn[id*2+1][0]);
	mn[id][1] = min(mn[id*2][1], mn[id*2+1][1]);
	mx[id][0] = max(mx[id*2][0], mx[id*2+1][0]);
	mx[id][1] = max(mx[id*2][1], mx[id*2+1][1]);
	sz[id][0] = sz[id*2][0] + sz[id*2+1][0];
	sz[id][1] = sz[id*2][1] + sz[id*2+1][1];
}
int main()
{
	scanf("%lld %lld", &n, &q);
	pii c[n];
	for(int i=0; i<n; i++)
	scanf("%lld %lld", &a[i], &b[i]), c[i] = mp(a[i], b[i]);
	sort(c, c+n);
	for(int i=0; i<n; i++)
	a[i] = c[i].f, b[i] = c[i].s;
	build(0, n-1, 1);
	//print(0, n-1, 1);
	//cout << sum << endl;
	while(q--)
	{
		ll x;
		scanf("%lld", &x);
		query(0, n-1, 1, x);
	}
	printf("%lld\n", sz[1][0]);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:85:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &a[i], &b[i]), c[i] = mp(a[i], b[i]);
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Correct 12 ms 688 KB Output is correct
4 Correct 18 ms 688 KB Output is correct
5 Correct 12 ms 796 KB Output is correct
6 Correct 12 ms 796 KB Output is correct
7 Correct 4 ms 796 KB Output is correct
8 Correct 4 ms 796 KB Output is correct
9 Correct 4 ms 796 KB Output is correct
10 Correct 5 ms 796 KB Output is correct
11 Correct 4 ms 796 KB Output is correct
12 Correct 5 ms 796 KB Output is correct
13 Correct 4 ms 796 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Correct 12 ms 688 KB Output is correct
4 Correct 18 ms 688 KB Output is correct
5 Correct 12 ms 796 KB Output is correct
6 Correct 12 ms 796 KB Output is correct
7 Correct 4 ms 796 KB Output is correct
8 Correct 4 ms 796 KB Output is correct
9 Correct 4 ms 796 KB Output is correct
10 Correct 5 ms 796 KB Output is correct
11 Correct 4 ms 796 KB Output is correct
12 Correct 5 ms 796 KB Output is correct
13 Correct 4 ms 796 KB Output is correct
14 Correct 1528 ms 2936 KB Output is correct
15 Execution timed out 3055 ms 5224 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Correct 12 ms 688 KB Output is correct
4 Correct 18 ms 688 KB Output is correct
5 Correct 12 ms 796 KB Output is correct
6 Correct 12 ms 796 KB Output is correct
7 Correct 4 ms 796 KB Output is correct
8 Correct 4 ms 796 KB Output is correct
9 Correct 4 ms 796 KB Output is correct
10 Correct 5 ms 796 KB Output is correct
11 Correct 4 ms 796 KB Output is correct
12 Correct 5 ms 796 KB Output is correct
13 Correct 4 ms 796 KB Output is correct
14 Correct 1528 ms 2936 KB Output is correct
15 Execution timed out 3055 ms 5224 KB Time limit exceeded
16 Halted 0 ms 0 KB -