Submission #286687

#	Time	Username	Problem	Language	Result	Execution time	Memory
286687		FEDIKUS	Quality Of Living (IOI10_quality)	C++17	60 / 100	5035 ms	54380 KiB

quality

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#include "quality.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

vector<int> fwt;

void dodaj(int x,int koliko){
    for(;x<fwt.size();x+=x&-x) fwt[x]+=koliko;
}

int upit(int x){
    int ret=0;
    for(;x>0;x-=x&-x) ret+=fwt[x];
    return ret;
}

int tren(int H,int W){
    int l=1;
    int r=fwt.size()-1;
    //cout<<"     "<<upit(fwt.size()-1)<<endl;
    int naj=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        int sta=upit(mid);
        if(sta>W*H/2+1){
            r=mid-1;
        }else if(sta==W*H/2+1){
            naj=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return naj;
}

void uradi(int i1,int i2,int j,int koliko,int** novoQ){
    for(;i1<=i2;i1++){
        dodaj(novoQ[i1][j],koliko);
    }
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int ret=INT_MAX;
    fwt.resize(R*C+1,0);
    int** novoQ=new int*[3001];
    for(int i=0;i<=3000;i++){
        novoQ[i]=new int[3001];
    }
    for(int i=0;i<=3000;i++){
        for(int j=0;j<3000;j++) novoQ[i][j]=Q[i][j];
    }
    for(int i=0;i<=R-H;i++){
        for(int j=0;j<W;j++){
            uradi(i,i+H-1,j,1,novoQ);
        }
        ret=min(ret,tren(H,W));
        //cout<<i<<" "<<W-1<<" "<<tren(H,W)<<endl;
        for(int j=W;j<C;j++){
            uradi(i,i+H-1,j-W,-1,novoQ);
            uradi(i,i+H-1,j,1,novoQ);
            ret=min(ret,tren(H,W));
            //cout<<i<<" "<<j<<" "<<tren(H,W)<<endl;
        }
        for(int j=C-1;j>=C-W;j--){
            uradi(i,i+H-1,j,-1,novoQ);
            //cout<<i<<" "<<j<<" "<<tren(H,W)<<endl;
        }
    }
    return ret;
}

Compilation message (stderr)

quality.cpp: In function 'void dodaj(int, int)':
quality.cpp:30:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(;x<fwt.size();x+=x&-x) fwt[x]+=koliko;
      |          ~^~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20