Submission #740964

#	Time	Username	Problem	Language	Result	Execution time	Memory
740964		vjudge1	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	411 ms	238380 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//** har vaght m2 ghabool shodi javabetoo midam (radal) **
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<ll , ll>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 5e2 + 6;
const long long mod = 998244353;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
ll l,r,mid;
ll n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
ll darage[maxm] , ss , mm;
queue<int> q;
vector<int> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm] , gos[maxm];
ll pedaret[10000000];
ll get_par(ll v){
    if (pedaret[v]==v) return v;
    return pedaret[v] = get_par(pedaret[v]);
}
void merge(ll r , ll q){
    if (get_par(r)!=get_par(q))l+=max(darage[r],darage[q])*1ll*sath[r]*1ll*sath[q];
    r = get_par(r) , q = get_par(q);
    if (r!=q){
        if (sath[r]<sath[q]) swap(r,q);
        pedaret[q] = r;
        sath[r] += sath[q];
    }
    return ;
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
set<ll> st , wtf , ajab;
ll dp[maxm];
ll rp[maxm];
pi w[maxm],ww[maxm];
//ll rw[maxm][maxm];
set<ll> ts[maxm] , jav[maxm];
ll rgh[maxm] , lft[maxm];
void solve(){
    if (l<=n){
        r = 1;
        for (int i=1; i<=n; i++) darage[i] = pedaret[i];
        for (int i=l; i; i--) darage[r] += i , r ++;
        sort(darage+1,darage+n+1);
        cout<<darage[1]<<endl;
        return ;
    }
    if ((l-n)%2==0){
        st.clear();
        for (int i=l; i>=l-n+1; i--) st.insert(i);
        ll rt = *st.begin();
        for (int i=1; i<=n; i++) darage[i] = pedaret[i];
        for (int i=1; i<=n; i++) darage[i] += *st.rbegin() , st.erase(*st.rbegin());
        sort(darage+1,darage+n+1);
        ll lx = 0 , rx = darage[1]+1;
        while (rx-lx>1){
            ll lm = (lx+rx)/2;
            bool ok = 0;
            mm = (l-n+1)/2;
            ll ans = 0;
            for (int i=1; i<=n; i++){
                ans+=darage[i]-lm;
            }
            if (ans>=mm) lx = lm;
            else rx = lm; 
        }
        cout<<lx<<endl;
        return;
    }
    st.clear();
    for (int i=l; i>=l-n+2; i--) st.insert(i);
    ll rt = *st.begin();
    for (int i=1; i<=n; i++) darage[i] = pedaret[i];
    for (int i=1; i<n; i++) darage[i] += *st.rbegin() , st.erase(*st.rbegin());
    
    sort(darage+1,darage+n+1);
    ll lx = -mod , rx = darage[1]+1;
    if ((l-n)%2==1){
        while (rx-lx>1){
            ll lm = (lx+rx)/2;
            bool ok = 0;
            mm = (l-n+1)/2;
            ll ans = 0;
            for (int i=1; i<=n; i++){
                ans+=darage[i]-lm;
            }
            if (ans>=mm) lx = lm;
            else rx = lm; 
        }
        cout<<lx<<endl;
        return;
    }
}
int xl[3002][3002][3] , yl[3002][3002][3];
short a[3002][3002];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >>n>>m;
    for (int i=1; i<=n; i++){
        string s;
        cin >>s;
        for (int j=1; j<=s.size(); j++){
            if (s[j-1]=='J') a[i][j] = 0;
            else if (s[j-1]=='O') a[i][j] = 1;
            else a[i][j] = 2;
        }
    }
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            for (int k=0; k<3; k++) xl[i][j][k] = xl[i][j-1][k] , yl[j][i][k] = yl[j][i-1][k];
            xl[i][j][a[i][j]]++;
            yl[j][i][a[i][j]]++;
        }
    }
    mid = 0;
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            mid += (a[i][j]==0) * (xl[i][m][1] - xl[i][j][1]) * (yl[j][n][2] - yl[j][i][2]);
        }
    }
    cout<<mid<<endl;
}

Compilation message (stderr)

joi2019_ho_t1.cpp: In function 'void solve()':
joi2019_ho_t1.cpp:71:18: warning: unused variable 'ok' [-Wunused-variable]
   71 |             bool ok = 0;
      |                  ^~
joi2019_ho_t1.cpp:64:12: warning: unused variable 'rt' [-Wunused-variable]
   64 |         ll rt = *st.begin();
      |            ^~
joi2019_ho_t1.cpp:94:18: warning: unused variable 'ok' [-Wunused-variable]
   94 |             bool ok = 0;
      |                  ^~
joi2019_ho_t1.cpp:85:8: warning: unused variable 'rt' [-Wunused-variable]
   85 |     ll rt = *st.begin();
      |        ^~
joi2019_ho_t1.cpp: In function 'int main()':
joi2019_ho_t1.cpp:115:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for (int j=1; j<=s.size(); j++){
      |                       ~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50