| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 847743 |
2023-09-10T09:58:26 Z |
HoriaHaivas |
RMQ (NOI17_rmq) |
C++14 |
|
1 ms |
8696 KB |
/*
"TLE is like the wind, always by my side"
- Yasuo - 2022 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
using namespace std;
struct qq
{
int l;
int r;
int x;
};
struct ptval
{
int nr;
int poz;
};
ptval val[100001];
const int inf=INT_MAX;
qq query[100001];
qq query2[100001];
qq aux[100001];
qq aux2[100001];
int st[100001];
int finl[100001];
bool placed[100001];
bool used[100001];
int lazy[400001];
int aint[400001];
bool cmp (qq a, qq b)
{
if (a.x!=b.x)
return a.x<b.x;
else if (a.l!=b.l)
return a.l<b.l;
else
return a.r<b.r;
}
bool cmp2(ptval a, ptval b)
{
if (a.nr!=b.nr)
return a.nr>b.nr;
else
return a.poz<b.poz;
}
bool cmp3 (qq a, qq b)
{
if (a.l!=b.l)
return a.l<b.l;
else if (a.r!=b.r)
return a.r<b.r;
else
return a.x<b.x;
}
void propagate(int parent, int child)
{
lazy[child]=lazy[parent];
}
void lazy_update (int l, int r, int val, int qa, int qb, int x)
{
if (lazy[val]!=-1)
{
if (r!=l)
{
propagate(val,val*2);
propagate(val,val*2+1);
}
lazy[val]=-1;
}
if (l>qb || r<qa)
return;
if (qa<=l && r<=qb)
{
lazy[val]=x;
return;
}
int mid;
mid=(l+r)/2;
if (qa<=mid)
lazy_update(l,mid,val*2,qa,qb,x);
if (qb>mid)
lazy_update(mid+1,r,val*2+1,qa,qb,x);
}
int qry (int l, int r, int val, int qa, int qb)
{
if (qa<=l && r<=qb)
{
return lazy[val];
}
if (lazy[val]!=-1)
{
if (r!=l)
{
propagate(val,val*2);
propagate(val,val*2+1);
}
lazy[val]=-1;
}
if (r<qa || l>qb)
return inf;
int mid,ans;
mid=(l+r)/2;
ans=inf;
if (qa<=mid)
ans=min(ans,qry(l,mid,val*2,qa,qb));
if (qb>mid)
ans=min(ans,qry(mid+1,r,val*2+1,qa,qb));
return ans;
}
void build(int l, int r, int val)
{
if (l==r)
{
aint[val]=finl[l];
return;
}
int mid;
mid=(l+r)/2;
build(l,mid,val*2);
build(mid+1,r,val*2+1);
aint[val]=min(aint[val*2],aint[val*2+1]);
}
int que(int l, int r, int val, int qa, int qb)
{
if (r<qa || l>qb)
return inf;
if (qa<=l && r<=qb)
return aint[val];
int mid,ans;
mid=(l+r)/2;
ans=inf;
if (qa<=mid)
ans=min(ans,que(l,mid,val*2,qa,qb));
if (qb>mid)
ans=min(ans,que(mid+1,r,val*2+1,qa,qb));
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
int n,q,i,j,t,q2,big,dif,y,res;
bool ok;
ok=true;
cin >> n >> q;
y=q;
for (i=1; i<=q; i++)
{
cin >> query[i].l >> query[i].r >> query[i].x;
aux2[i]=query[i];
query2[i]=query[i];
}
sort(query+1,query+1+q,cmp);
sort(query2+1,query2+1+q,cmp);
t=0;
for (j=1; j<=q; j++)
{
if (t==0 || query[j].x!=query[st[t]].x || (query[j].r<query[st[t]].l || query[j].l>query[st[t]].r))
{
t++;
st[t]=j;
}
else
{
query[st[t]].l=max(query[st[t]].l,query[j].l);
query[st[t]].r=min(query[st[t]].r,query[j].r);
}
}
q2=q;
q=t;
while (t>0)
{
aux[t]=query[st[t]];
t--;
}
for (j=1; j<=q; j++)
{
query[j]=aux[j];
if (query[j].l==query[j-1].l && query[j].r==query[j-1].r && query[j].x!=query[j-1].x)
ok=false;
}
t=0;
for (j=1; j<=q2; j++)
{
///cout << query2[j].l << " " << query2[j].r << " " << query2[j].x << "\n";
if (t==0 || query2[j].x!=query2[st[t]].x || (query2[j].r<query2[st[t]].l || query2[j].l>query2[st[t]].r))
{
t++;
st[t]=j;
}
else
{
query2[st[t]].l=min(query2[st[t]].l,query2[j].l);
query2[st[t]].r=max(query2[st[t]].r,query2[j].r);
}
}
q2=t;
while (t>0)
{
aux[t]=query2[st[t]];
t--;
}
for (j=1; j<=q2; j++)
{
query2[j]=aux[j];
if (query2[j].l==query2[j-1].l && query2[j].r==query2[j-1].r && query2[j].x!=query2[j-1].x)
ok=false;
}
for (j=0; j<=4*n; j++)
{
lazy[j]=-1;
}
for (j=1; j<=q2; j++)
{
lazy_update(1,n,1,query2[j].l+1,query2[j].r+1,query2[j].x);
}
for (j=1; j<=n; j++)
{
val[j].nr=qry(1,n,1,j,j);
val[j].poz=j;
finl[j]=val[j].nr;
}
if (ok==false)
{
for (j=1; j<=n; j++)
{
cout << -1 << " ";
}
}
else
{
for (j=1;j<=n;j++)
{
cout << finl[j] << " ";
}
}
return 0;
}
Compilation message
rmq.cpp: In function 'int main()':
rmq.cpp:159:22: warning: unused variable 'big' [-Wunused-variable]
159 | int n,q,i,j,t,q2,big,dif,y,res;
| ^~~
rmq.cpp:159:26: warning: unused variable 'dif' [-Wunused-variable]
159 | int n,q,i,j,t,q2,big,dif,y,res;
| ^~~
rmq.cpp:159:30: warning: variable 'y' set but not used [-Wunused-but-set-variable]
159 | int n,q,i,j,t,q2,big,dif,y,res;
| ^
rmq.cpp:159:32: warning: unused variable 'res' [-Wunused-variable]
159 | int n,q,i,j,t,q2,big,dif,y,res;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
8696 KB |
Output is partially correct |
| 2 |
Partially correct |
1 ms |
8536 KB |
Output is partially correct |
| 3 |
Partially correct |
1 ms |
8540 KB |
Output is partially correct |
| 4 |
Partially correct |
1 ms |
8540 KB |
Output is partially correct |
| 5 |
Partially correct |
1 ms |
8536 KB |
Output is partially correct |
| 6 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
8696 KB |
Output is partially correct |
| 2 |
Partially correct |
1 ms |
8536 KB |
Output is partially correct |
| 3 |
Partially correct |
1 ms |
8540 KB |
Output is partially correct |
| 4 |
Partially correct |
1 ms |
8540 KB |
Output is partially correct |
| 5 |
Partially correct |
1 ms |
8536 KB |
Output is partially correct |
| 6 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
8696 KB |
Output is partially correct |
| 2 |
Partially correct |
1 ms |
8536 KB |
Output is partially correct |
| 3 |
Partially correct |
1 ms |
8540 KB |
Output is partially correct |
| 4 |
Partially correct |
1 ms |
8540 KB |
Output is partially correct |
| 5 |
Partially correct |
1 ms |
8536 KB |
Output is partially correct |
| 6 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
