Submission #956485

#	Time	Username	Problem	Language	Result	Execution time	Memory
956485		modwwe	Nekameleoni (COCI15_nekameleoni)	C++17	140 / 140	1270 ms	163412 KiB

nekameleoni

#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 (stderr)

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++)
      |          ^~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14