#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
//#define int long long
#define down cout<<'\n';
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
void phongbeo();
mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count ());
const int mod2=1e9+7;
const int mod1=998244353;
struct ib
{
int a;
int b;
};
struct icd
{
int a,b;
};
struct ic
{
int a,b,c;
};
struct id
{
int a,b,c,d;
};
int minn=1e12+1,maxx=-1e9;
int n,m,s2,s4,s3,sf,k,r,dem=0,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,l;
int s,i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
//fin(task),fou(task);
#endif
NHP
//modwwe
phongbeo(),down
checktime
}
struct freestyle{
int a;ib ck[51];
} t[400001];
ib t2[51],t3[51];
int a[100001];
int subset(int x,int y)
{
if((x|y)==(1ll<<k)-1) return 1;
return 0;
}
bool cmp(ib a,ib b)
{
return a.a>b.a;
}
void ff(int x,int c,int y)
{
t[x].a=min(t[x<<1].a,t[x<<1|1].a);
for(int i=1;i<=k;i++)
t[x].ck[i].a=min(t[x<<1].ck[i].a,t[x<<1|1].ck[i].a),
t[x].ck[i].b=max(t[x<<1].ck[i].b,t[x<<1|1].ck[i].b),
t2[i].a=t[x<<1].ck[i].b,
t2[i].b=i;
for(int i=1;i<=k;i++)
if(t[x].ck[i].a==1e9)
return;
sort(t2+1,t2+1+k,cmp);
t[0].a=c-1;
s3=c-1;
for(int i=k;i>=0;--i)
{t[x].a=min(s3-t2[i].a+1,t[x].a);
s3=max(s3,t[x<<1|1].ck[t2[i].b].a);
if(s3==1e9) return;
//if(y==2&&c==2)
//cout<<t[x].a<<" "<<s3<<" "<<t2[i].a<<" "<<i<<" "<<t2[i].b<<" "<<t2[1].a<<" "<<t2[1].b,down
}
}
void upd(int node,int l,int r,int l1,int r1,int x,int z)
{
if(l>r1||r<l1) return ;
if(l>=l1&&r<=r1) {
t[node].ck[x].a=l1;
t[node].ck[x].b=l1;
if(x!=z) t[node].ck[z].a=1e9;
if(x!=z)t[node].ck[z].b=-1e9;
return;
}
int mid=l+r>>1;
if(l1<=mid)upd(node<<1,l,mid,l1,r1,x,z);
else upd(node<<1|1,mid+1,r,l1,r1,x,z);
// if(l1==3) cout<<l<<" "<<r,down
//if(l1==4) cout<<t[x].a<<" "<<l<<" "<<r<<" "<<t[x<<1].a,down
ff(node,mid+1,l1);
}
void phongbeo()
{
cin>>n>>k>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=4*n;i++)
{t[i].a=1e9;
for(int j=1;j<=k;j++)
t[i].ck[j].a=1e9,
t[i].ck[j].b=-1e9;
}
for(int i=1;i<=n;++i)
upd(1,1,n,i,i,a[i],0);
for(i=1;i<=m;++i)
{
cin>>l;
if(l==2)
{
if(t[1].a>n) cout<<-1;
else cout<<t[1].a;
down
}
else
{ cin>>l>>r;
upd(1,1,n,l,l,r,a[l]);
a[l]=r;
}
}
}
Compilation message
nekameleoni.cpp:38:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.000000000001e+12' to '2147483647' [-Woverflow]
38 | int minn=1e12+1,maxx=-1e9;
| ~~~~^~
nekameleoni.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
42 | main()
| ^~~~
nekameleoni.cpp: In function 'void upd(int, int, int, int, int, int, int)':
nekameleoni.cpp:98:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
98 | int mid=l+r>>1;
| ~^~
nekameleoni.cpp: In function 'void phongbeo()':
nekameleoni.cpp:108:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
108 | for(int i=1;i<=n;i++)
| ^~~
nekameleoni.cpp:110:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
110 | for(int i=1;i<=4*n;i++)
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
284 ms |
35820 KB |
Output is correct |
| 2 |
Correct |
243 ms |
115444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
597 ms |
89240 KB |
Output is correct |
| 2 |
Correct |
335 ms |
154300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
631 ms |
68444 KB |
Output is correct |
| 2 |
Correct |
289 ms |
133348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
910 ms |
107072 KB |
Output is correct |
| 2 |
Correct |
287 ms |
139604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
859 ms |
99636 KB |
Output is correct |
| 2 |
Correct |
302 ms |
148056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1270 ms |
163384 KB |
Output is correct |
| 2 |
Correct |
309 ms |
163152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1216 ms |
163412 KB |
Output is correct |
| 2 |
Correct |
374 ms |
163344 KB |
Output is correct |
