oj.uz

Submission #867568

# Submission time Handle Problem Language Result Execution time Memory
867568 2023-10-28T19:19:16 Z JakobZorz Rectangles (IOI19_rect) C++14
37 / 100
 5000 ms 1048576 KB 
#include"rect.h"
#include<algorithm>
#include<unordered_set>
#include<set>
#include<iostream>
using namespace std;
typedef long long ll;

unordered_set<int>intersect(unordered_set<int>&a,unordered_set<int>&b){
    if(a.size()>b.size())
        return intersect(b,a);
    unordered_set<int>res;
    for(int i:a)
        if(b.find(i)!=b.end())
            res.insert(i);
    return res;
}

unordered_set<int>gaps_right[2500][2500];
unordered_set<int>gaps_down[2500][2500];
int arr[2500][2500];
int w,h;

bool cmp1(pair<int,int>&a,pair<int,int>&b){
    if(a.first!=b.first)
        return a.first>b.first;
    return a.second>b.second;
}

bool cmp2(pair<int,int>&a,pair<int,int>&b){
    if(a.first!=b.first)
        return a.first>b.first;
    return a.second<b.second;
}

void process_column(int x){
    vector<pair<int,int>>vals(h);
    for(int y=0;y<h;y++)
        vals[y]={arr[x][y],y};
    sort(vals.begin(),vals.end(),cmp1);
    set<int>s;
    for(auto [_val,i]:vals){
        auto iter=s.insert(i).first;
        auto next=iter;
        next++;
        
        if(next!=s.end()){
            if(*next-i-1!=0)
                gaps_down[x][i].insert(*next-i-1);
        }
    }
    
    sort(vals.begin(),vals.end(),cmp2);
    s.clear();
    for(auto [_val,i]:vals){
        auto iter=s.insert(i).first;
        auto prev=iter;
        if(prev!=s.begin()){
            prev--;
            if(i-*prev-1!=0)
                gaps_down[x][*prev].insert(i-*prev-1);
        }
    }
}

void process_row(int y){
    vector<pair<int,int>>vals(w);
    for(int x=0;x<w;x++)
        vals[x]={arr[x][y],x};
    sort(vals.begin(),vals.end(),cmp1);
    set<int>s;
    for(auto [_val,i]:vals){
        s.insert(i);
        auto iter=s.find(i);
        auto next=iter;
        next++;
        
        if(next!=s.end()){
            if(*next-i-1!=0)
                gaps_right[i][y].insert(*next-i-1);
        }
    }
    
    sort(vals.begin(),vals.end(),cmp2);
    s.clear();
    for(auto [_val,i]:vals){
        auto iter=s.insert(i).first;
        auto prev=iter;
        if(prev!=s.begin()){
            prev--;
            if(i-*prev-1!=0)
                gaps_right[*prev][y].insert(i-*prev-1);
        }
    }
}

ll count(int x,int y,int width){
    unordered_set<int>s=gaps_down[x][y-1];
    for(int i=0;i<width;i++){
        s=intersect(s,gaps_down[x+i][y-1]);
    }
    ll res=0;
    int maxh=h-y;
    for(int y2=y;y2<h;y2++){
        if(gaps_right[x-1][y2].find(width)==gaps_right[x-1][y2].end()){
            maxh=y2-y;
            break;
        }
    }
    for(int height:s)
        if(height<=maxh)
            res++;
    /*for(int height:s){
        bool valid=true;
        for(int y2=y;y2<y+height;y2++){
            if(gaps_right[x-1][y2].find(width)==gaps_right[x-1][y2].end()){
                valid=false;
                break;
            }
        }
        
        if(valid)
            res++;
    }*/
    //cout<<"x: "<<x<<", y: "<<y<<", width: "<<width<<": "<<res<<"\n";
    return res;
}

ll count_rectangles(vector<vector<int>>a_){
    h=(int)a_.size();
    w=(int)a_[0].size();
    for(int x=0;x<w;x++){
        for(int y=0;y<h;y++){
            arr[x][y]=a_[y][x];
        }
    }
    
    for(int x=0;x<w;x++)
        process_column(x);
    
    for(int y=0;y<h;y++)
        process_row(y);
    
    ll res=0;
    for(int x=1;x<w-1;x++)
        for(int y=1;y<h-1;y++)
            for(int width:gaps_right[x-1][y])
                res+=count(x,y,width);
    
	return res;
}

Compilation message

rect.cpp: In function 'void process_column(int)':
rect.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [_val,i]:vals){
      |              ^
rect.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for(auto [_val,i]:vals){
      |              ^
rect.cpp: In function 'void process_row(int)':
rect.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for(auto [_val,i]:vals){
      |              ^
rect.cpp:86:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |     for(auto [_val,i]:vals){
      |              ^
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:145:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  145 |     for(int x=1;x<w-1;x++)
      |     ^~~
rect.cpp:150:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  150 |  return res;
      |  ^~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 686872 KB Output is correct
2 Correct 165 ms 689372 KB Output is correct
3 Correct 158 ms 689232 KB Output is correct
4 Correct 161 ms 689344 KB Output is correct
5 Correct 160 ms 689036 KB Output is correct
6 Correct 154 ms 689252 KB Output is correct
7 Correct 155 ms 687188 KB Output is correct
8 Correct 154 ms 689124 KB Output is correct
9 Correct 165 ms 689156 KB Output is correct
10 Correct 174 ms 689100 KB Output is correct
11 Correct 161 ms 689316 KB Output is correct
12 Correct 163 ms 689332 KB Output is correct
13 Correct 157 ms 686888 KB Output is correct
14 Correct 154 ms 686932 KB Output is correct
15 Correct 172 ms 686928 KB Output is correct
16 Correct 163 ms 686936 KB Output is correct
17 Correct 155 ms 686996 KB Output is correct
18 Correct 154 ms 686952 KB Output is correct
19 Correct 174 ms 689236 KB Output is correct
20 Correct 159 ms 687112 KB Output is correct
21 Correct 157 ms 686932 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 686872 KB Output is correct
2 Correct 165 ms 689372 KB Output is correct
3 Correct 158 ms 689232 KB Output is correct
4 Correct 161 ms 689344 KB Output is correct
5 Correct 160 ms 689036 KB Output is correct
6 Correct 154 ms 689252 KB Output is correct
7 Correct 155 ms 687188 KB Output is correct
8 Correct 154 ms 689124 KB Output is correct
9 Correct 165 ms 689156 KB Output is correct
10 Correct 174 ms 689100 KB Output is correct
11 Correct 161 ms 689316 KB Output is correct
12 Correct 163 ms 689332 KB Output is correct
13 Correct 157 ms 686888 KB Output is correct
14 Correct 154 ms 686932 KB Output is correct
15 Correct 172 ms 686928 KB Output is correct
16 Correct 163 ms 686936 KB Output is correct
17 Correct 155 ms 686996 KB Output is correct
18 Correct 154 ms 686952 KB Output is correct
19 Correct 174 ms 689236 KB Output is correct
20 Correct 159 ms 687112 KB Output is correct
21 Correct 157 ms 686932 KB Output is correct
22 Correct 220 ms 691028 KB Output is correct
23 Correct 209 ms 690872 KB Output is correct
24 Correct 211 ms 690784 KB Output is correct
25 Correct 170 ms 689832 KB Output is correct
26 Correct 181 ms 690256 KB Output is correct
27 Correct 164 ms 690224 KB Output is correct
28 Correct 162 ms 690064 KB Output is correct
29 Correct 161 ms 689452 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 686872 KB Output is correct
2 Correct 165 ms 689372 KB Output is correct
3 Correct 158 ms 689232 KB Output is correct
4 Correct 161 ms 689344 KB Output is correct
5 Correct 160 ms 689036 KB Output is correct
6 Correct 154 ms 689252 KB Output is correct
7 Correct 155 ms 687188 KB Output is correct
8 Correct 154 ms 689124 KB Output is correct
9 Correct 165 ms 689156 KB Output is correct
10 Correct 174 ms 689100 KB Output is correct
11 Correct 161 ms 689316 KB Output is correct
12 Correct 163 ms 689332 KB Output is correct
13 Correct 157 ms 686888 KB Output is correct
14 Correct 154 ms 686932 KB Output is correct
15 Correct 172 ms 686928 KB Output is correct
16 Correct 163 ms 686936 KB Output is correct
17 Correct 220 ms 691028 KB Output is correct
18 Correct 209 ms 690872 KB Output is correct
19 Correct 211 ms 690784 KB Output is correct
20 Correct 170 ms 689832 KB Output is correct
21 Correct 181 ms 690256 KB Output is correct
22 Correct 164 ms 690224 KB Output is correct
23 Correct 162 ms 690064 KB Output is correct
24 Correct 161 ms 689452 KB Output is correct
25 Correct 155 ms 686996 KB Output is correct
26 Correct 154 ms 686952 KB Output is correct
27 Correct 174 ms 689236 KB Output is correct
28 Correct 159 ms 687112 KB Output is correct
29 Correct 157 ms 686932 KB Output is correct
30 Correct 1135 ms 701268 KB Output is correct
31 Correct 1084 ms 701248 KB Output is correct
32 Correct 1040 ms 701244 KB Output is correct
33 Correct 193 ms 693328 KB Output is correct
34 Correct 211 ms 696308 KB Output is correct
35 Correct 216 ms 696148 KB Output is correct
36 Correct 215 ms 695852 KB Output is correct
37 Correct 209 ms 695776 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 686872 KB Output is correct
2 Correct 165 ms 689372 KB Output is correct
3 Correct 158 ms 689232 KB Output is correct
4 Correct 161 ms 689344 KB Output is correct
5 Correct 160 ms 689036 KB Output is correct
6 Correct 154 ms 689252 KB Output is correct
7 Correct 155 ms 687188 KB Output is correct
8 Correct 154 ms 689124 KB Output is correct
9 Correct 165 ms 689156 KB Output is correct
10 Correct 174 ms 689100 KB Output is correct
11 Correct 161 ms 689316 KB Output is correct
12 Correct 163 ms 689332 KB Output is correct
13 Correct 157 ms 686888 KB Output is correct
14 Correct 154 ms 686932 KB Output is correct
15 Correct 172 ms 686928 KB Output is correct
16 Correct 163 ms 686936 KB Output is correct
17 Correct 220 ms 691028 KB Output is correct
18 Correct 209 ms 690872 KB Output is correct
19 Correct 211 ms 690784 KB Output is correct
20 Correct 170 ms 689832 KB Output is correct
21 Correct 181 ms 690256 KB Output is correct
22 Correct 164 ms 690224 KB Output is correct
23 Correct 162 ms 690064 KB Output is correct
24 Correct 161 ms 689452 KB Output is correct
25 Correct 1135 ms 701268 KB Output is correct
26 Correct 1084 ms 701248 KB Output is correct
27 Correct 1040 ms 701244 KB Output is correct
28 Correct 193 ms 693328 KB Output is correct
29 Correct 211 ms 696308 KB Output is correct
30 Correct 216 ms 696148 KB Output is correct
31 Correct 215 ms 695852 KB Output is correct
32 Correct 209 ms 695776 KB Output is correct
33 Correct 155 ms 686996 KB Output is correct
34 Correct 154 ms 686952 KB Output is correct
35 Correct 174 ms 689236 KB Output is correct
36 Correct 159 ms 687112 KB Output is correct
37 Correct 157 ms 686932 KB Output is correct
38 Correct 1573 ms 771828 KB Output is correct
39 Correct 1515 ms 747412 KB Output is correct
40 Correct 1572 ms 747420 KB Output is correct
41 Execution timed out 5023 ms 723036 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 711248 KB Output is correct
2 Correct 673 ms 711096 KB Output is correct
3 Correct 160 ms 709780 KB Output is correct
4 Correct 160 ms 686984 KB Output is correct
5 Correct 165 ms 710584 KB Output is correct
6 Correct 175 ms 710620 KB Output is correct
7 Correct 165 ms 710620 KB Output is correct
8 Correct 163 ms 710484 KB Output is correct
9 Correct 164 ms 710484 KB Output is correct
10 Correct 160 ms 709972 KB Output is correct
11 Correct 160 ms 710276 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 686996 KB Output is correct
2 Correct 154 ms 686952 KB Output is correct
3 Correct 174 ms 689236 KB Output is correct
4 Correct 159 ms 687112 KB Output is correct
5 Correct 157 ms 686932 KB Output is correct
6 Correct 154 ms 686928 KB Output is correct
7 Correct 2851 ms 936396 KB Output is correct
8 Runtime error 3472 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 686872 KB Output is correct
2 Correct 165 ms 689372 KB Output is correct
3 Correct 158 ms 689232 KB Output is correct
4 Correct 161 ms 689344 KB Output is correct
5 Correct 160 ms 689036 KB Output is correct
6 Correct 154 ms 689252 KB Output is correct
7 Correct 155 ms 687188 KB Output is correct
8 Correct 154 ms 689124 KB Output is correct
9 Correct 165 ms 689156 KB Output is correct
10 Correct 174 ms 689100 KB Output is correct
11 Correct 161 ms 689316 KB Output is correct
12 Correct 163 ms 689332 KB Output is correct
13 Correct 157 ms 686888 KB Output is correct
14 Correct 154 ms 686932 KB Output is correct
15 Correct 172 ms 686928 KB Output is correct
16 Correct 163 ms 686936 KB Output is correct
17 Correct 220 ms 691028 KB Output is correct
18 Correct 209 ms 690872 KB Output is correct
19 Correct 211 ms 690784 KB Output is correct
20 Correct 170 ms 689832 KB Output is correct
21 Correct 181 ms 690256 KB Output is correct
22 Correct 164 ms 690224 KB Output is correct
23 Correct 162 ms 690064 KB Output is correct
24 Correct 161 ms 689452 KB Output is correct
25 Correct 1135 ms 701268 KB Output is correct
26 Correct 1084 ms 701248 KB Output is correct
27 Correct 1040 ms 701244 KB Output is correct
28 Correct 193 ms 693328 KB Output is correct
29 Correct 211 ms 696308 KB Output is correct
30 Correct 216 ms 696148 KB Output is correct
31 Correct 215 ms 695852 KB Output is correct
32 Correct 209 ms 695776 KB Output is correct
33 Correct 1573 ms 771828 KB Output is correct
34 Correct 1515 ms 747412 KB Output is correct
35 Correct 1572 ms 747420 KB Output is correct
36 Execution timed out 5023 ms 723036 KB Time limit exceeded
37 Halted 0 ms 0 KB -