| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 988712 |
2024-05-25T16:50:06 Z |
Acanikolic |
RMQ (NOI17_rmq) |
C++14 |
|
2 ms |
6500 KB |
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
const long long N = 2e5 + 10;
const long long mod = 998244353;
const long long inf = 1e9;
vector<pair<int,int>>g[N];
int seg[N],lazy[N];
void push(int node,int tl,int tr) {
seg[node] += lazy[node];
if(tl != tr) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
void modify(int node,int tl,int tr,int l,int r,int x) {
push(node,tl,tr);
if(tl > r || tr < l) return;
if(tl >= l && tr <= r) {
lazy[node] += x;
push(node,tl,tr);
return;
}
push(node,tl,tr);
int mid = (tl + tr) / 2;
modify(node * 2,tl,mid,l,r,x);
modify(node * 2 + 1,mid + 1,tr,l,r,x);
seg[node] = max(seg[node * 2],seg[node * 2 + 1]);
}
int get(int node,int tl,int tr,int l,int r) {
push(node,tl,tr);
if(tl > r || tr < l) return 0;
if(tl >= l && tr <= r) return seg[node];
int mid = (tl + tr) / 2;
return max(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r));
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,q;
cin >> n >> q;
vector<int>res(n + 1);
for(int i = 1; i <= q; i++) {
int l,r,x;
cin >> l >> r >> x;
l += 1;
r += 1;
x += 1;
g[x].pb({l,r});
}
set<int>st;
for(int i = 1; i <= n; i++) st.insert(i);
vector<int>vec;
bool ok = true;
for(int i = n; i >= 1; i--) {
if(!g[i].size()) {
vec.pb(i);
continue;
}
vector<int>all;
for(auto X : g[i]) {
int cnt = 0;
auto lb = st.lower_bound(X.F);
vector<int>v;
while(lb != st.end() && *lb <= X.S) {
cnt += 1;
v.pb(*lb);
all.pb(*lb);
lb++;
}
for(auto XX : v) {
st.erase(XX);
}
modify(1,1,n,X.F,X.S,1);
}
if(get(1,1,n,1,n) != g[i].size()) {
ok = false;
goto kraj;
}
bool used = false;
for(auto X : all) {
if(!used && get(1,1,n,X,X) == g[i].size()) {
used = true;
res[X] = i;
continue;
}
if(vec.empty()) {
ok = false;
goto kraj;
}
res[X] = vec.back();
vec.pop_back();
}
for(auto X : all) modify(1,1,n,X,X,-1);
}
kraj:;
if(ok) {
for(int i = 1; i <= n; i++) cout << res[i] - 1 << " ";
}else {
for(int i = 1; i <= n; i++) cout << -1 << " ";
}
return 0;
}
Compilation message
rmq.cpp: In function 'int main()':
rmq.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | if(get(1,1,n,1,n) != g[i].size()) {
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rmq.cpp:99:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | if(!used && get(1,1,n,X,X) == g[i].size()) {
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
