| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1037268 |
2024-07-28T11:58:53 Z |
Ludissey |
Fire (BOI24_fire) |
C++17 |
|
0 ms |
348 KB |
#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
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]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
