oj.uz

Submission #740964

# Submission time Handle Problem Language Result Execution time Memory
740964 2023-05-13T10:33:46 Z vjudge1 Bitaro the Brave (JOI19_ho_t1) C++17
100 / 100
 411 ms 238380 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 1 ms 1720 KB Output is correct
8 Correct 2 ms 1848 KB Output is correct
9 Correct 1 ms 1748 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 2 ms 1844 KB Output is correct
12 Correct 1 ms 1748 KB Output is correct
13 Correct 1 ms 1720 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 1 ms 1720 KB Output is correct
8 Correct 2 ms 1848 KB Output is correct
9 Correct 1 ms 1748 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 2 ms 1844 KB Output is correct
12 Correct 1 ms 1748 KB Output is correct
13 Correct 1 ms 1720 KB Output is correct
14 Correct 9 ms 11024 KB Output is correct
15 Correct 2 ms 3924 KB Output is correct
16 Correct 6 ms 7892 KB Output is correct
17 Correct 1 ms 1748 KB Output is correct
18 Correct 12 ms 13048 KB Output is correct
19 Correct 10 ms 12736 KB Output is correct
20 Correct 9 ms 12800 KB Output is correct
21 Correct 11 ms 13040 KB Output is correct
22 Correct 9 ms 12776 KB Output is correct
23 Correct 10 ms 12860 KB Output is correct
24 Correct 12 ms 13012 KB Output is correct
25 Correct 9 ms 12656 KB Output is correct
26 Correct 10 ms 12884 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 1 ms 1720 KB Output is correct
8 Correct 2 ms 1848 KB Output is correct
9 Correct 1 ms 1748 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 2 ms 1844 KB Output is correct
12 Correct 1 ms 1748 KB Output is correct
13 Correct 1 ms 1720 KB Output is correct
14 Correct 9 ms 11024 KB Output is correct
15 Correct 2 ms 3924 KB Output is correct
16 Correct 6 ms 7892 KB Output is correct
17 Correct 1 ms 1748 KB Output is correct
18 Correct 12 ms 13048 KB Output is correct
19 Correct 10 ms 12736 KB Output is correct
20 Correct 9 ms 12800 KB Output is correct
21 Correct 11 ms 13040 KB Output is correct
22 Correct 9 ms 12776 KB Output is correct
23 Correct 10 ms 12860 KB Output is correct
24 Correct 12 ms 13012 KB Output is correct
25 Correct 9 ms 12656 KB Output is correct
26 Correct 10 ms 12884 KB Output is correct
27 Correct 411 ms 232040 KB Output is correct
28 Correct 10 ms 19900 KB Output is correct
29 Correct 32 ms 29004 KB Output is correct
30 Correct 6 ms 10324 KB Output is correct
31 Correct 273 ms 188156 KB Output is correct
32 Correct 364 ms 237612 KB Output is correct
33 Correct 378 ms 237928 KB Output is correct
34 Correct 344 ms 209564 KB Output is correct
35 Correct 377 ms 237616 KB Output is correct
36 Correct 380 ms 237932 KB Output is correct
37 Correct 379 ms 238380 KB Output is correct
38 Correct 283 ms 186704 KB Output is correct
39 Correct 257 ms 187444 KB Output is correct