Submission #61897187

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
//#define int long long 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
mt19937_64 rnd(time(0));
const int N = 5e5 + 10;
int n;
template<typename T>
struct SegTree //sum
{
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
//#define int long long 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
mt19937_64 rnd(time(0));

const int N = 5e5 + 10;

int n;

template<typename T>
struct SegTree //sum
{
    struct Node
    {
        int l, r;
        T sum, maxv, minv, add;
    }tr[N * 4];

    #define lc p<<1
    #define rc p<<1|1

    void pushup(int p)
    {
        tr[p].sum = tr[lc].sum + tr[rc].sum;
		tr[p].maxv = max(tr[lc].maxv, tr[rc].maxv);
		tr[p].minv = min(tr[lc].minv, tr[rc].minv);
    }

    void pushdown(int p)
    {
        if (tr[p].add)
        {
            tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1);
            tr[rc].sum += tr[p].add * (tr[rc].r - tr[rc].l + 1);
			tr[lc].maxv += tr[p].add;
			tr[rc].maxv += tr[p].add;
			tr[lc].minv += tr[p].add;
			tr[rc].minv += tr[p].add;
            tr[lc].add += tr[p].add;
            tr[rc].add += tr[p].add;
            tr[p].add = 0;
        }
    }

    void build(int p, int l, int r,auto arr)
    {
        tr[p] = { l,r,arr[l],arr[l],arr[l], 0 };
        if (l == r) return;
        int mid = l + r >> 1;
        build(lc, l, mid , arr);
        build(rc, mid + 1, r , arr);
        pushup(p);
    }

    void update(int p, int l, int r, T k)
    {
        if (l <= tr[p].l && tr[p].r <= r)
        {
            tr[p].sum += 1LL * (tr[p].r - tr[p].l + 1) * k;
			tr[p].maxv += k;
			tr[p].minv += k;
            tr[p].add += k;
            return;
        }
        int mid = tr[p].l + tr[p].r >> 1;
        pushdown(p);
        if (l <= mid) update(lc, l ,r, k);
        if (r > mid)  update(rc, l ,r, k);
        pushup(p);
    }

    T querysum(int p, int l, int r)
    {
        if (l <= tr[p].l && tr[p].r <= r)
            return tr[p].sum;
        int mid = tr[p].l + tr[p].r >> 1;
        pushdown(p);
        T sum = 0;
        if (l <= mid) sum += querysum(lc, l, r);
        if (r > mid) sum += querysum(rc, l, r);
        return sum;
    }

    T querymax(int p, int l, int r)
    {
        if (l <= tr[p].l && tr[p].r <= r) return tr[p].maxv;
        pushdown(p);
        int mid = tr[p].l + tr[p].r >> 1;
        T maxv = INT_MIN;
        if (l <= mid) maxv = max(maxv, querymax(lc, l, r));
        if (r > mid) maxv = max(maxv, querymax(rc, l, r));
        return maxv;
    }

    T querymin(int p, int l, int r)
    {
        if (l <= tr[p].l && tr[p].r <= r) return tr[p].minv;
        pushdown(p);
        int mid = tr[p].l + tr[p].r >> 1;
        T minv = INT_MAX;
        if (l <= mid) minv = min( minv , querymin(lc, l, r));
        if (r > mid) minv = min(minv, querymin(rc, l, r));
        return minv;
    }
};

SegTree<int> seg;

int binary_search1(int x){
	int lo = 0, hi = 5e5 + 1;
	while(lo + 1 < hi){
		int mid = lo + hi >> 1;
		if(seg.querymax(1,1,mid) < x){
			lo = mid;
		}
		else{
			hi = mid;
		}
	} 
	return hi;
}

int binary_search2(int x){
	int lo = 0, hi = 5e5 + 1;
	while(lo + 1 < hi){
		int mid = lo + hi >> 1;
		if(seg.querymin(1,mid,5e5) > x){
			hi = mid;
		}
		else{
			lo = mid;
		}
	}
	return lo;
}


void solve()
{	
	int a[N];
	for(int i = 1; i <= 5e5; i++){
		a[i] = i;
	}
	
	seg.build(1,1,5e5,a);

	cin >> n;
	for(int i = 1; i <= n; i++){
		int l,r;
		cin >> l >> r;
		l = binary_search1(l);
		r = binary_search2(r);
		seg.update(1,l,r,1);
	}

	int q;
	cin >> q;
	while(q--){
		int x;
		cin >> x;
		cout << seg.querysum(1,x,x) << endl;
	}
}


signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T=1; //cin>>T;
	while(T--) solve();
	return 0;
}

Submission Info

Compile Error

Main.cpp:54:36: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   54 |     void build(int p, int l, int r,auto arr)
      |                                    ^~~~
Main.cpp: In function ‘int binary_search1(int)’:
Main.cpp:121:30: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  121 |                 int mid = lo + hi >> 1;
      |                           ~~~^~~~
Main.cpp: In function ‘int binary_search2(int)’:
Main.cpp:135:30: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  135 |                 int mid = lo + hi >> 1;
      |                           ~~~^~~~
Main.cpp: In instantiation of ‘T SegTree<T>::querymax(int, int, int) [with T = int]’:
Main.cpp:122:18:   required from here
Main.cpp:97:27: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   97 |         int mid = tr[p].l + tr[p].r >> 1;
      |                   ~~~~~~~~^~~~~~~~~
Main.cpp: In instantiation of ‘T SegTree<T>::querymin(int, int, int) [with T = int]’:
Main.cpp:136:18:   required from here
Main.cpp:108:27: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  108 |         int mid = tr[p].l + tr[p].r >> 1;
      |                   ~~~~~~~~^~~~~~~~~
Main.cpp: In instantiation of ‘void SegTree<T>::build(int, int, int, auto:28) [with auto:28 = int*; T = int]’:
Main.cpp:154:11:   required from here
Main.cpp:58:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   58 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In instantiation of ‘void SegTree<T>::update(int, int, int, T) [with T = int]’:
Main.cpp:162:13:   required from here
Main.cpp:74:27: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   74 |         int mid = tr[p].l + tr[p].r >> 1;
      |                   ~~~~~~~~^~~~~~~~~
Main.cpp: In instantiation of ‘T SegTree<T>::querysum(int, int, int) [with T = int]’:
Main.cpp:170:23:   required from here
Main.cpp:85:27: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   85 |         int mid = tr[p].l + tr[p].r >> 1;
      |                   ~~~~~~~~^~~~~~~~~

Judge Result