/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 21ms 3.613 MiB
#4 Accepted 52ms 7.086 MiB
#5 Accepted 254ms 33.363 MiB
#6 Accepted 460ms 95.0 MiB
#7 Accepted 477ms 65.293 MiB
#8 Accepted 325ms 27.754 MiB
#9 Accepted 409ms 21.504 MiB
#10 Accepted 398ms 22.262 MiB
#11 Accepted 423ms 17.582 MiB
#12 Accepted 252ms 7.754 MiB
#13 Accepted 1216ms 36.781 MiB
#14 Accepted 1201ms 36.719 MiB
#15 Accepted 1652ms 36.75 MiB
#16 Accepted 1585ms 37.496 MiB
#17 Accepted 699ms 36.715 MiB
#18 Accepted 99ms 16.816 MiB
#19 Accepted 690ms 135.383 MiB
#20 Accepted 1ms 320.0 KiB
#21 Accepted 68ms 13.52 MiB
#22 Accepted 73ms 13.52 MiB
#23 Accepted 237ms 36.871 MiB
#24 Accepted 944ms 37.594 MiB
#25 Accepted 269ms 37.41 MiB
#26 Accepted 901ms 36.859 MiB

Code

/*
 *   Copyright (c) 2025 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.second == b.second) return a.first<b.first;
    return a.second<b.second;
}

struct node {
    struct node *left=NULL,*right=NULL;
    int cnt=0;
};

void update(node *&root,int start,int end,int ind)
{
    if(root->left==NULL) root->left = new node();
    if(root->right==NULL) root->right = new node();
    if(start==end)
    {
        root->cnt=1;
        return;
    }
    int mid = (start+end)/2;
    if(ind<=mid) update(root->left,start,mid,ind);
    else update(root->right,mid+1,end,ind);
    root->cnt = root->left->cnt + root->right->cnt;
}

int query(node *&root,int start,int end,int l,int r)
{
    if(root==NULL) return 0;
    if(l>end || r<start) return 0;
    if(l<=start && r>=end) return root->cnt;
    int mid = (start+end)/2;
    int x = query(root->left,start,mid,l,r);
    int y = query(root->right,mid+1,end,l,r);
    return x+y;
}

int freee(node *&root,int l,int r)
{
    int lo=l,hi=r,mid,x=-1;
    while(lo<=hi)
    {
        int mid =(lo+hi)/2;
        int d = mid-l+1;
        int sum = query(root,1,1e9,l,mid);
        if(sum < d)
        {
            x = mid;
            hi = mid-1;
        }else lo=mid+1;
    }
    return x;
}

void solve()
{
    int n; cin >> n;
    vector<pair<int,int>> v;
    for(int i=0;i<n;i++)
    {
        int l,r; cin >> l >> r;
        v.push_back({l,r});
    }
    sort(v.begin(),v.end(),cmp);
    set<int> ans;
    node *root = new node();

    for(auto e:v)
    {
        int r = e.second;
        int l = e.first;
        int free = freee(root,l,r);
        if(free==-1)
        {
            cout<<"NO"<<endl;
            return;
        }
        ans.insert(free);
        update(root,1,1e9,free);
    }
    cout<<"YES"<<endl;
    for(auto e:ans) cout<<e<<' '; cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int t; cin >> t; while(t--) solve();
}

Information

Submit By
Type
Submission
Problem
P1185 Segment
Language
C++17 (G++ 13.2.0)
Submit At
2025-04-05 20:10:40
Judged At
2025-04-05 20:10:40
Judged By
Score
100
Total Time
1652ms
Peak Memory
135.383 MiB