Submission #1039728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039728		Andrey	Gift Exchange (JOI24_ho_t4)	C++14	100 / 100	1354 ms	197064 KiB

Main

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> haha(500001);
vector<int> seg(4000001,-1);
vector<int> wow(4000001,-1);
vector<pair<int,int>> bruh(500001);
vector<pair<int,int>> wut[2000001];
int no;
bool yeah = true;

void upd(int l, int r, int ql, int qr, int x, int br) {
    no = max(no,wow[x]);
    if(l == ql && r == qr) {
        no = max(no,seg[x]);
        wow[x] = max(wow[x],br);
        seg[x] = max(seg[x],wow[x]);
        return;
    }
    int mid = (l+r)/2;
    if(qr <= mid) {
        upd(l,mid,ql,qr,x*2,br);
    }
    else if(ql > mid) {
        upd(mid+1,r,ql,qr,x*2+1,br);
    }
    else {
        upd(l,mid,ql,mid,x*2,br);
        upd(mid+1,r,mid+1,qr,x*2+1,br);
    }
    seg[x] = max(wow[x],seg[x*2]);
    seg[x] = max(seg[x],seg[x*2+1]);
}

void build(int l, int r, int x) {
    for(int i = l; i <= r; i++) {
        wut[x].push_back(bruh[i]);
    }
    sort(wut[x].begin(),wut[x].end());
    for(int i = 1; i < wut[x].size(); i++) {
        wut[x][i] = {wut[x][i].first,max(wut[x][i].second,wut[x][i-1].second)};
    }
    if(l == r) {
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
}

void dude(int l, int r, int ql, int qr, int x, int s, int b) {
    if(l == ql && r == qr) {
        if(wut[x][0].first >= s) {
            return;
        }
        int bl = 0,br = wut[x].size()-1;
        while(bl < br) {
            int mid = (bl+br+1)/2;
            if(wut[x][mid].first < s) {
                bl = mid;
            }
            else {
                br = mid-1;
            }
        }
        if(wut[x][bl].second > b) {
            yeah = false;
        }
        return;
    }
    int mid = (l+r)/2;
    if(qr <= mid) {
        dude(l,mid,ql,qr,x*2,s,b);
    }
    else if(ql > mid) {
        dude(mid+1,r,ql,qr,x*2+1,s,b);
    }
    else {
        dude(l,mid,ql,mid,x*2,s,b);
        dude(mid+1,r,mid+1,qr,x*2+1,s,b);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,a,b;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a;
        haha[i] = {0,a};
    }
    for(int i = 1; i <= n; i++) {
        cin >> a;
        haha[i] = {a,haha[i].second};
    }
    for(int i = 1; i <= n; i++) {
        no = -1;
        upd(1,2*n,haha[i].first,haha[i].second,1,i);
        bruh[i] = {no,0};
    }
    for(int i = 0; i < seg.size(); i++) {
        seg[i] = -1;
        wow[i] = -1;
    }
    for(int i = n; i >= 1; i--) {
        no = -1;
        upd(1,2*n,haha[i].first,haha[i].second,1,n-i+1);
        bruh[i] = {bruh[i].first,n-no+1};
    }
    build(1,n,1);
    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> a >> b;
        yeah = true;
        dude(1,n,a,b,1,a,b);
        if(yeah) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 1; i < wut[x].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i = 0; i < seg.size(); i++) {
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 31 / 31
• Subtask 5: 8 / 8
• Subtask 6: 12 / 12
• Subtask 7: 18 / 18
• Subtask 8: 12 / 12