#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 print(int l, int r, int id)
{
if(t[id][0])
{
t[id][0] = 0;
swap(mn[id][0], mn[id][1]);
swap(mx[id][0], mx[id][1]);
if(l != r)
t[id*2][0] ^= 1, t[id*2+1][0] ^= 1;
}
cout << l << " " << r << endl;
cout << mx[id][0] << " " << mn[id][0] << " | ";
cout << mx[id][1] << " " << mn[id][1] << endl;
if(l == r)
return ;
int mid = (l+r)>>1;
print(l, mid, id*2);
print(mid+1, r, id*2+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()
{
cin >> n >> q;
for(int i=0; i<n; i++)
cin >> a[i] >> b[i];
build(0, n-1, 1);
//print(0, n-1, 1);
//cout << sum << endl;
while(q--)
{
ll x;
cin >> x;
query(0, n-1, 1, x);
}
cout << sz[1][0] << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
