Submission #341276

#	Time	Username	Problem	Language	Result	Execution time	Memory
341276		beksultan04	K blocks (IZhO14_blocks)	C++14	0 / 100	16 ms	23788 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scanl(a) scanf("%lld",&a);
#define scanll(a,b) scanf("%lld %lld",&a, &b);
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define scan1(a) scanf("%d",&a);
#define scan2(a,b) scanf("%d %d",&a, &b);
#define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
#define eps 1e-12
const int N = 1e6+12;
const ll INF=1e15+7;
int q[N],n,ansmx=0,der[N];
vector <int>g[N];
bool vis[N];
void update(int v,int l,int r,int x){
    if (l == r){
        der[v]=x;
        ret ;
    }
    int m = l+r>>1;
    if (m < x)
        update((v<<1)+1,m+1,r,x);
    else update(v<<1,l,m,x);
    der[v] = der[v<<1]+der[(v<<1)+1];
}


int get_ans(int v,int l,int r,int ql,int qr){
    if (l > qr || r < ql)ret 0;
    if (ql <= l && r <= qr){
        ret der[v];
    }
    int m = l+r>>1;
    ret get_ans(v<<1,l,m,ql,qr)+get_ans((v<<1)+1,m+1,r,ql,qr);
}


void dfs(int x,int mx){
    vis[x] = 1;
    max(mx,q[x]);
    ansmx = max(ansmx,mx);

    for (int i=0;i<g[x].size();++i){
        if (vis[g[x][i]]==0){
            dfs(g[x][i],mx);
        }
    }
}


main(){
    int i,k,ans,sum=0,cou=0;
    scan2(n,k)
    ans=n;
    vector <pii> v;
    for (i=1;i<=n;++i){
        scan1(q[i])
        sum+=q[i];
        v.pb({q[i],i});
    }
    sort(allr(v));
    for (i=0;i<n;++i){
        if (ans == k)break;
        update(1,1,n,v[i].sc);
        if (get_ans(1,1,n,v[i].sc+1,v[i].sc+1)){
            g[v[i].sc+1].pb(v[i].sc);
            sum -= q[v[i].sc+1];
            ans--;
            g[v[i].sc].pb(v[i].sc+1);
        }
        if (ans == k)break;
        if (get_ans(1,1,n,v[i].sc-1,v[i].sc-1)){
            ans--;
            sum -= q[v[i].sc-1];
            g[v[i].sc-1].pb(v[i].sc);
            g[v[i].sc].pb(v[i].sc-1);
        }

    }
    for (i=n;i>0;--i){
        if (vis[i] == 0){
            dfs(i,0);
            cou += q[i];
        }
    }
    cout <<cou;





}

Compilation message (stderr)

blocks.cpp: In function 'void update(int, int, int, int)':
blocks.cpp:33:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int m = l+r>>1;
      |             ~^~
blocks.cpp: In function 'int get_ans(int, int, int, int, int)':
blocks.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int m = l+r>>1;
      |             ~^~
blocks.cpp: In function 'void dfs(int, int)':
blocks.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i=0;i<g[x].size();++i){
      |                  ~^~~~~~~~~~~~
blocks.cpp: At global scope:
blocks.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main(){
      |      ^
blocks.cpp: In function 'int main()':
blocks.cpp:15:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 | #define scan2(a,b) scanf("%d %d",&a, &b);
      |                    ~~~~~^~~~~~~~~~~~~~~~
blocks.cpp:66:5: note: in expansion of macro 'scan2'
   66 |     scan2(n,k)
      |     ^~~~~
blocks.cpp:14:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 | #define scan1(a) scanf("%d",&a);
      |                  ~~~~~^~~~~~~~~
blocks.cpp:70:9: note: in expansion of macro 'scan1'
   70 |         scan1(q[i])
      |         ^~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47