Submission #1037268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037268		Ludissey	Fire (BOI24_fire)	C++17	0 / 100	0 ms	348 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;


struct node {
	int sum,index;
	node* left, *right;
	void update() {
		sum = max(left->sum,right->sum);
        if(left->sum > right->sum) index=left->index;
        else index=right->index;
 	}
};

pair<int,int> query(node* root, int left, int right, int qLeft, int qRight) {
	if (left > qRight || right < qLeft) return {0,0};
	if (left >= qLeft && right <= qRight) return {root->sum, root->index};
	int mid = (left + right) / 2;
    pair<int,int> l=query(root->left, left, mid, qLeft, qRight);
    pair<int,int> r=query(root->right, mid + 1, right, qLeft, qRight);
    if(l.first>r.first) return l;
    else return r;
}

void build(node* root, int left, int right, const vector<int>& v) {
	if (left == right) {
		root->sum = v[left];
        root->index=left;
		return;
	}
	int mid = (left + right) / 2;
	root->left = new node{ NULL, NULL, 0,0 };
	root->right = new node{ NULL, NULL, 0,0 };
	build(root->left, left, mid, v);
	build(root->right, mid+1, right, v);
	root->update();
}
node* root;
vector<pair<int,int>> a;
vector<int> nxt;
vector<int> depth;
vector<vector<int>> pref;
vector<int> maxindex;
int n,m;
void dfs(int x, int d){
    for (auto u : pref[x]) dfs(u,d+1);
    depth[x]=d;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    a.resize(n);
    nxt.resize(n,-1);
    pref.resize(n);

    maxindex.resize(n,n-1);

    for (int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
        if(a[i].first>a[i].second) a[i].second+=m;
    }
    vector<int> forseg(n);
    sort(a.begin(),a.end());
    for (int i = 0; i < n; i++) forseg[i]=a[i].second;
    root=new node{ NULL, NULL, 0,0 };
    build(root, 0,n-1,forseg);
    vector<int> dp(n);
    for (int i = 0; i < n; i++)
    {
        int l=0, r=n;
        while(l<r){
            int mid=(l+r)/2;
            if(a[mid].first>a[i].second){
                r=mid;
            }else {
                l=mid+1;
            }
        }
        nxt[i]=query(root,0,n-1,i,l-1).second;
        if(nxt[i]==i) nxt[i]=-1;
        else pref[nxt[i]].push_back(i);  
    }
    int mn=1e9;
    depth.resize(n);
    for (int i = 0; i < n; i++){
        if(nxt[i]==-1) dfs(i,0);
    }
    
    node *root2=new node{0,0,NULL,NULL};
    build(root2, 0,n-1,depth);
    for (int i = 0; i < n; i++){
        if(a[i].second>=m){
            int l=0, r=n;
            while(l<r){
                int mid=(l+r)/2;
                if(a[mid].first>a[i].second-m){
                    r=mid;
                }else {
                    l=mid+1;
                }
            }
            if(l==0) continue;
            mn=min(mn, query(root2,0,n-1,0,l).first-depth[i]);
        }
    }

    if(mn==1e9) cout << -1 << "\n";
    else cout << mn << "\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build(node*, long long int, long long int, const std::vector<long long int>&)':
Main.cpp:36:41: warning: converting to non-pointer type 'long long int' from NULL [-Wconversion-null]
   36 |  root->left = new node{ NULL, NULL, 0,0 };
      |                                         ^
Main.cpp:36:41: warning: converting to non-pointer type 'long long int' from NULL [-Wconversion-null]
Main.cpp:37:42: warning: converting to non-pointer type 'long long int' from NULL [-Wconversion-null]
   37 |  root->right = new node{ NULL, NULL, 0,0 };
      |                                          ^
Main.cpp:37:42: warning: converting to non-pointer type 'long long int' from NULL [-Wconversion-null]
Main.cpp: In function 'int main()':
Main.cpp:70:36: warning: converting to non-pointer type 'long long int' from NULL [-Wconversion-null]
   70 |     root=new node{ NULL, NULL, 0,0 };
      |                                    ^
Main.cpp:70:36: warning: converting to non-pointer type 'long long int' from NULL [-Wconversion-null]

• Subtask 1: 0 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26