oj.uz

Submission #1034764

# Submission time Handle Problem Language Result Execution time Memory
1034764 2024-07-25T17:36:05 Z tosivanmak Rectangles (IOI19_rect) C++17
72 / 100
 1695 ms 1048576 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll lg[1000005];
struct Sparse_Table_Max{
//   vector<vector<int> >stmax;
int stmax[2501][12];
    // vector<ll>arr;
    int arr[2501];
    void init(ll n){
        // stmax.resize(n+5);
        // for(int i=0;i<n+5;i++){
            // stmax[i].resize(12);
        // }
        // arr.resize(n+5);
    }
    void build(ll n){
        for(int i=1;i<=n;i++){
            stmax[i][0]=arr[i];
        }
        for(int j=1;j<=11;j++){
            for(int i=1;i<=n;i++){
                if(i+(1<<(j-1))<=n){
                    stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
                }
            }
        }
    }
    ll qry(ll ql, ll qr){
        ll rng=lg[qr-ql+1];
        return max(stmax[ql][rng],stmax[qr-(1<<rng)+1][rng]);
    }
};
struct Sparse_Table_Min{
    int stmin[2501][12];
    int arr[2501];
    void init(ll n){
        
    }
    void build(ll n){
        for(int i=1;i<=n;i++){
            stmin[i][0]=arr[i];
        }
        for(int j=1;j<=11;j++){
            for(int i=1;i<=n;i++){
                if(i+(1<<(j-1))<=n){
                    stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
                }
            }
        }
    }
    ll qry(ll ql, ll qr){
        ll rng=lg[qr-ql+1];
        return min(stmin[ql][rng],stmin[qr-(1<<rng)+1][rng]);
    }  
};
struct Fenwick{
  vector<int>tree;
    void init(ll n){
        tree.resize(n+5,0);
    }
    void upd(ll n, ll m, ll val){
        for(int i=n;i<=m;i+=(i&(-i))){
            tree[i]+=val;
        }
    }
    void reset(ll n, ll m){
        for(int i=n;i<=m;i+=(i&(-i))){
            tree[i]=0;
        }
    }
    ll sum(ll e){
        ll s=0;
        while(e>=1){
            s+=tree[e]; e-=(e&(-e));
        }
        return s;
    }
    ll qry(ll ql, ll qr){
        return sum(qr)-sum(ql-1);
    }
}BIT;
struct Union_Find{
    vector<int>fa,siz,lef,righ;
    void init(ll n){
        fa.resize(n+5),siz.resize(n+5);
        lef.resize(n+5),righ.resize(n+5);
        for(int i=1;i<=n;i++){
            fa[i]=i,siz[i]=1,lef[i]=righ[i]=i;
        }
    }
    ll root(ll x){
        if(fa[x]==x)return x;
        return fa[x]=root(fa[x]);
    }
    void unite(ll u, ll v){
        u=root(u),v=root(v);
        if(siz[u]<siz[v])swap(u,v);
        siz[u]+=siz[v],fa[v]=u;
        lef[u]=min(lef[u],lef[v]);righ[u]=max(righ[u],righ[v]);
    }
    void clear(){
        lef.clear(),righ.clear(),siz.clear(),fa.clear();
    }
}dsu;
Sparse_Table_Min spmin[2505];
Sparse_Table_Max spmax[2505];
ll n,m;
int grid[2505][2505];
int maxi[2505][2505],mini[2505][2505];
vector<pair<int,int> >ope[2505];
vector<int>ele[2505];
vector<pair<int,int> >hv[2505];
vector<pair<int,int> >all;
vector<int>inside[10000005];
void proc(ll id){
    vector<ll>srt;
    for(int i=1;i<=m;i++){
       srt.push_back(grid[id][i]);
    }
    sort(srt.begin(),srt.end());
    srt.erase(unique(srt.begin(),srt.end()),srt.end());
    for(int i=1;i<=m;i++){
        ll it=lower_bound(srt.begin(),srt.end(),grid[id][i])-srt.begin()+1;
        ele[it].push_back(i);
    }
    vector<pair<int,int> >ss;
    dsu.init(m);
    bool merged[m+5];
    for(int i=1;i<=m;i++)merged[i]=0;
    for(int i=1;i<=srt.size();i++){
        for(auto& u: ele[i]){
            if(u!=1){
                if(merged[u-1])dsu.unite(u,u-1);
            }
            if(u!=m){
                if(merged[u+1])dsu.unite(u,u+1);
            }
            merged[u]=1;
        }
        for(auto& u: ele[i]){
            ll f=dsu.root(u);
            ll l=dsu.lef[f],r=dsu.righ[f];
            if(l!=1&&r!=m){
                ss.push_back({l,r});
            }
        }
    }
    sort(ss.begin(),ss.end());
    ss.erase(unique(ss.begin(),ss.end()),ss.end());
    for(int i=1;i<=srt.size();i++)ele[i].clear();
    dsu.clear();
    hv[id]=ss;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size(),m=a[0].size();
    for(int i=2;i<=1000000;i*=2){
        lg[i]=1;
    }
    for(int i=3;i<=1000000;i++){
        lg[i]+=lg[i-1];
    }
    if(n<=2||m<=2)return 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            grid[i+1][j+1]=a[i][j];
        }
    }
    for(int i=2;i<n;i++){
        proc(i);
    }
    stack<pair<ll,ll> >sta;
    for(int j=2;j<m;j++){
        for(int i=1;i<=n;i++){
            if(sta.size()==0){
                sta.push({grid[i][j],i});
            }
            else{
                while(sta.size()){
                    ll lol=sta.top().first;
                    if(lol<=grid[i][j]){
                        maxi[sta.top().second][j]=i-1;
                        sta.pop();
                    }
                    else{
                        break;
                    }
                }
                sta.push({grid[i][j],i});
            }
        }
        while(sta.size()){
            maxi[sta.top().second][j]=10000;
            sta.pop();
        }
    }
    for(int j=2;j<m;j++){
        for(int i=n;i>=1;i--){
            if(sta.size()==0){
                sta.push({grid[i][j],i});
            }
            else{
                while(sta.size()){
                    ll lol=sta.top().first;
                    if(lol<=grid[i][j]){
                        mini[sta.top().second][j]=i+1;
                        sta.pop();
                    }
                    else{
                        break;
                    }
                }
                sta.push({grid[i][j],i});
            }
        }
        while(sta.size()){
            mini[sta.top().second][j]=-10000;
            sta.pop();
        }
    }
    for(int i=1;i<=n;i++){
        for(auto& u: hv[i]){
            all.push_back(u);
        }
    }
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());
    for(int i=1;i<=n;i++){
        spmin[i].init(m),spmax[i].init(m);
        for(int j=1;j<=m;j++){
            spmin[i].arr[j]=maxi[i][j];
            spmax[i].arr[j]=mini[i][j];
        }
        spmin[i].build(m),spmax[i].build(m);
    }
    for(int i=1;i<=n;i++){
        for(auto& u: hv[i]){
            ll hsh=lower_bound(all.begin(),all.end(),u)-all.begin()+1;
            inside[hsh].push_back(i);
        }
    }
    ll answer=0;
    BIT.init(n);
    ll tot=all.size();
    for(int i=1;i<=tot;i++){
        // cout<<all[i-1].first<<" "<<all[i-1].second<<":\n";
        ll lef=-1;
        vector<pair<int,int> >po;
        for(int j=0;j<inside[i].size();j++){
            // cout<<inside[i][j]<<'\n';
            if(j==0)lef=inside[i][j];
            else{
                if(inside[i][j]!=inside[i][j-1]+1){
                    po.push_back({lef,inside[i][j-1]});
                    lef=inside[i][j];
                }
            }
        }
        po.push_back({lef,inside[i][inside[i].size()-1]});
        for(auto& [l,r]: po){
            // cout<<l<<" "<<r<<'\n';
            for(int j=l-1;j<=r-1;j++){
                ope[j+1].push_back({j,1});
                ll nxt=spmin[j].qry(all[i-1].first,all[i-1].second)+1;
                if(nxt<=r){
                    ope[nxt].push_back({j,-1});
                }
            }
            for(int j=l;j<=r;j++){
                for(auto& k: ope[j]){
                    // cout<<"operation "<<k.first<<" "<<k.second<<'\n';
                    if(k.second==1)BIT.upd(k.first,n,1);
                    else BIT.upd(k.first,n,-1);
                }
                ll go=spmax[j+1].qry(all[i-1].first,all[i-1].second);
                go--;
                go=max(go,1LL);
                answer+=BIT.qry(go,j-1);
            }
            for(int j=l-1;j<=r;j++)BIT.reset(j,n),ope[j].clear();
            // cout<<answer<<'\n';
        }
        
    }
    return answer;
    // return -1;
}

Compilation message

rect.cpp: In function 'void proc(long long int)':
rect.cpp:133:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int i=1;i<=srt.size();i++){
      |                 ~^~~~~~~~~~~~
rect.cpp:153:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for(int i=1;i<=srt.size();i++)ele[i].clear();
      |                 ~^~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:251:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |         for(int j=0;j<inside[i].size();j++){
      |                     ~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 243372 KB Output is correct
2 Correct 113 ms 244220 KB Output is correct
3 Correct 104 ms 244040 KB Output is correct
4 Correct 100 ms 244048 KB Output is correct
5 Correct 104 ms 244048 KB Output is correct
6 Correct 90 ms 244052 KB Output is correct
7 Correct 95 ms 243904 KB Output is correct
8 Correct 95 ms 243536 KB Output is correct
9 Correct 98 ms 244048 KB Output is correct
10 Correct 94 ms 244048 KB Output is correct
11 Correct 96 ms 244052 KB Output is correct
12 Correct 112 ms 244120 KB Output is correct
13 Correct 96 ms 243024 KB Output is correct
14 Correct 131 ms 243024 KB Output is correct
15 Correct 134 ms 243428 KB Output is correct
16 Correct 133 ms 243280 KB Output is correct
17 Correct 98 ms 243024 KB Output is correct
18 Correct 98 ms 243224 KB Output is correct
19 Correct 102 ms 244048 KB Output is correct
20 Correct 106 ms 244052 KB Output is correct
21 Correct 105 ms 243216 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 243372 KB Output is correct
2 Correct 113 ms 244220 KB Output is correct
3 Correct 104 ms 244040 KB Output is correct
4 Correct 100 ms 244048 KB Output is correct
5 Correct 104 ms 244048 KB Output is correct
6 Correct 90 ms 244052 KB Output is correct
7 Correct 95 ms 243904 KB Output is correct
8 Correct 95 ms 243536 KB Output is correct
9 Correct 98 ms 244048 KB Output is correct
10 Correct 94 ms 244048 KB Output is correct
11 Correct 96 ms 244052 KB Output is correct
12 Correct 112 ms 244120 KB Output is correct
13 Correct 96 ms 243024 KB Output is correct
14 Correct 131 ms 243024 KB Output is correct
15 Correct 134 ms 243428 KB Output is correct
16 Correct 133 ms 243280 KB Output is correct
17 Correct 98 ms 243024 KB Output is correct
18 Correct 98 ms 243224 KB Output is correct
19 Correct 102 ms 244048 KB Output is correct
20 Correct 106 ms 244052 KB Output is correct
21 Correct 105 ms 243216 KB Output is correct
22 Correct 103 ms 246284 KB Output is correct
23 Correct 135 ms 246420 KB Output is correct
24 Correct 100 ms 246352 KB Output is correct
25 Correct 124 ms 246356 KB Output is correct
26 Correct 104 ms 246356 KB Output is correct
27 Correct 103 ms 246356 KB Output is correct
28 Correct 101 ms 246300 KB Output is correct
29 Correct 102 ms 245844 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 243372 KB Output is correct
2 Correct 113 ms 244220 KB Output is correct
3 Correct 104 ms 244040 KB Output is correct
4 Correct 100 ms 244048 KB Output is correct
5 Correct 104 ms 244048 KB Output is correct
6 Correct 90 ms 244052 KB Output is correct
7 Correct 95 ms 243904 KB Output is correct
8 Correct 95 ms 243536 KB Output is correct
9 Correct 98 ms 244048 KB Output is correct
10 Correct 94 ms 244048 KB Output is correct
11 Correct 96 ms 244052 KB Output is correct
12 Correct 112 ms 244120 KB Output is correct
13 Correct 96 ms 243024 KB Output is correct
14 Correct 131 ms 243024 KB Output is correct
15 Correct 134 ms 243428 KB Output is correct
16 Correct 133 ms 243280 KB Output is correct
17 Correct 103 ms 246284 KB Output is correct
18 Correct 135 ms 246420 KB Output is correct
19 Correct 100 ms 246352 KB Output is correct
20 Correct 124 ms 246356 KB Output is correct
21 Correct 104 ms 246356 KB Output is correct
22 Correct 103 ms 246356 KB Output is correct
23 Correct 101 ms 246300 KB Output is correct
24 Correct 102 ms 245844 KB Output is correct
25 Correct 98 ms 243024 KB Output is correct
26 Correct 98 ms 243224 KB Output is correct
27 Correct 102 ms 244048 KB Output is correct
28 Correct 106 ms 244052 KB Output is correct
29 Correct 105 ms 243216 KB Output is correct
30 Correct 126 ms 254940 KB Output is correct
31 Correct 122 ms 254816 KB Output is correct
32 Correct 111 ms 254924 KB Output is correct
33 Correct 121 ms 254288 KB Output is correct
34 Correct 122 ms 254692 KB Output is correct
35 Correct 122 ms 255080 KB Output is correct
36 Correct 119 ms 254928 KB Output is correct
37 Correct 144 ms 254676 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 243372 KB Output is correct
2 Correct 113 ms 244220 KB Output is correct
3 Correct 104 ms 244040 KB Output is correct
4 Correct 100 ms 244048 KB Output is correct
5 Correct 104 ms 244048 KB Output is correct
6 Correct 90 ms 244052 KB Output is correct
7 Correct 95 ms 243904 KB Output is correct
8 Correct 95 ms 243536 KB Output is correct
9 Correct 98 ms 244048 KB Output is correct
10 Correct 94 ms 244048 KB Output is correct
11 Correct 96 ms 244052 KB Output is correct
12 Correct 112 ms 244120 KB Output is correct
13 Correct 96 ms 243024 KB Output is correct
14 Correct 131 ms 243024 KB Output is correct
15 Correct 134 ms 243428 KB Output is correct
16 Correct 133 ms 243280 KB Output is correct
17 Correct 103 ms 246284 KB Output is correct
18 Correct 135 ms 246420 KB Output is correct
19 Correct 100 ms 246352 KB Output is correct
20 Correct 124 ms 246356 KB Output is correct
21 Correct 104 ms 246356 KB Output is correct
22 Correct 103 ms 246356 KB Output is correct
23 Correct 101 ms 246300 KB Output is correct
24 Correct 102 ms 245844 KB Output is correct
25 Correct 126 ms 254940 KB Output is correct
26 Correct 122 ms 254816 KB Output is correct
27 Correct 111 ms 254924 KB Output is correct
28 Correct 121 ms 254288 KB Output is correct
29 Correct 122 ms 254692 KB Output is correct
30 Correct 122 ms 255080 KB Output is correct
31 Correct 119 ms 254928 KB Output is correct
32 Correct 144 ms 254676 KB Output is correct
33 Correct 98 ms 243024 KB Output is correct
34 Correct 98 ms 243224 KB Output is correct
35 Correct 102 ms 244048 KB Output is correct
36 Correct 106 ms 244052 KB Output is correct
37 Correct 105 ms 243216 KB Output is correct
38 Correct 331 ms 337116 KB Output is correct
39 Correct 222 ms 337292 KB Output is correct
40 Correct 273 ms 337088 KB Output is correct
41 Correct 220 ms 337184 KB Output is correct
42 Correct 276 ms 336276 KB Output is correct
43 Correct 295 ms 336312 KB Output is correct
44 Correct 260 ms 336484 KB Output is correct
45 Correct 281 ms 330940 KB Output is correct
46 Correct 230 ms 326092 KB Output is correct
47 Correct 282 ms 327628 KB Output is correct
48 Correct 379 ms 335056 KB Output is correct
49 Correct 433 ms 337012 KB Output is correct
50 Correct 248 ms 300000 KB Output is correct
51 Correct 248 ms 290388 KB Output is correct
52 Correct 389 ms 335104 KB Output is correct
53 Correct 384 ms 335996 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 244356 KB Output is correct
2 Correct 112 ms 244360 KB Output is correct
3 Correct 98 ms 244304 KB Output is correct
4 Correct 104 ms 243248 KB Output is correct
5 Correct 103 ms 244336 KB Output is correct
6 Correct 101 ms 244372 KB Output is correct
7 Correct 112 ms 244280 KB Output is correct
8 Correct 101 ms 244352 KB Output is correct
9 Correct 116 ms 244560 KB Output is correct
10 Correct 99 ms 243304 KB Output is correct
11 Correct 100 ms 243280 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 243024 KB Output is correct
2 Correct 98 ms 243224 KB Output is correct
3 Correct 102 ms 244048 KB Output is correct
4 Correct 106 ms 244052 KB Output is correct
5 Correct 105 ms 243216 KB Output is correct
6 Correct 101 ms 243536 KB Output is correct
7 Correct 801 ms 627164 KB Output is correct
8 Correct 1695 ms 1045384 KB Output is correct
9 Correct 1650 ms 1048576 KB Output is correct
10 Correct 1663 ms 1048576 KB Output is correct
11 Correct 481 ms 623920 KB Output is correct
12 Correct 805 ms 994124 KB Output is correct
13 Correct 818 ms 1014344 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 243372 KB Output is correct
2 Correct 113 ms 244220 KB Output is correct
3 Correct 104 ms 244040 KB Output is correct
4 Correct 100 ms 244048 KB Output is correct
5 Correct 104 ms 244048 KB Output is correct
6 Correct 90 ms 244052 KB Output is correct
7 Correct 95 ms 243904 KB Output is correct
8 Correct 95 ms 243536 KB Output is correct
9 Correct 98 ms 244048 KB Output is correct
10 Correct 94 ms 244048 KB Output is correct
11 Correct 96 ms 244052 KB Output is correct
12 Correct 112 ms 244120 KB Output is correct
13 Correct 96 ms 243024 KB Output is correct
14 Correct 131 ms 243024 KB Output is correct
15 Correct 134 ms 243428 KB Output is correct
16 Correct 133 ms 243280 KB Output is correct
17 Correct 103 ms 246284 KB Output is correct
18 Correct 135 ms 246420 KB Output is correct
19 Correct 100 ms 246352 KB Output is correct
20 Correct 124 ms 246356 KB Output is correct
21 Correct 104 ms 246356 KB Output is correct
22 Correct 103 ms 246356 KB Output is correct
23 Correct 101 ms 246300 KB Output is correct
24 Correct 102 ms 245844 KB Output is correct
25 Correct 126 ms 254940 KB Output is correct
26 Correct 122 ms 254816 KB Output is correct
27 Correct 111 ms 254924 KB Output is correct
28 Correct 121 ms 254288 KB Output is correct
29 Correct 122 ms 254692 KB Output is correct
30 Correct 122 ms 255080 KB Output is correct
31 Correct 119 ms 254928 KB Output is correct
32 Correct 144 ms 254676 KB Output is correct
33 Correct 331 ms 337116 KB Output is correct
34 Correct 222 ms 337292 KB Output is correct
35 Correct 273 ms 337088 KB Output is correct
36 Correct 220 ms 337184 KB Output is correct
37 Correct 276 ms 336276 KB Output is correct
38 Correct 295 ms 336312 KB Output is correct
39 Correct 260 ms 336484 KB Output is correct
40 Correct 281 ms 330940 KB Output is correct
41 Correct 230 ms 326092 KB Output is correct
42 Correct 282 ms 327628 KB Output is correct
43 Correct 379 ms 335056 KB Output is correct
44 Correct 433 ms 337012 KB Output is correct
45 Correct 248 ms 300000 KB Output is correct
46 Correct 248 ms 290388 KB Output is correct
47 Correct 389 ms 335104 KB Output is correct
48 Correct 384 ms 335996 KB Output is correct
49 Correct 103 ms 244356 KB Output is correct
50 Correct 112 ms 244360 KB Output is correct
51 Correct 98 ms 244304 KB Output is correct
52 Correct 104 ms 243248 KB Output is correct
53 Correct 103 ms 244336 KB Output is correct
54 Correct 101 ms 244372 KB Output is correct
55 Correct 112 ms 244280 KB Output is correct
56 Correct 101 ms 244352 KB Output is correct
57 Correct 116 ms 244560 KB Output is correct
58 Correct 99 ms 243304 KB Output is correct
59 Correct 100 ms 243280 KB Output is correct
60 Correct 101 ms 243536 KB Output is correct
61 Correct 801 ms 627164 KB Output is correct
62 Correct 1695 ms 1045384 KB Output is correct
63 Correct 1650 ms 1048576 KB Output is correct
64 Correct 1663 ms 1048576 KB Output is correct
65 Correct 481 ms 623920 KB Output is correct
66 Correct 805 ms 994124 KB Output is correct
67 Correct 818 ms 1014344 KB Output is correct
68 Correct 98 ms 243024 KB Output is correct
69 Correct 98 ms 243224 KB Output is correct
70 Correct 102 ms 244048 KB Output is correct
71 Correct 106 ms 244052 KB Output is correct
72 Correct 105 ms 243216 KB Output is correct
73 Runtime error 1645 ms 1048576 KB Execution killed with signal 9
74 Halted 0 ms 0 KB -