oj.uz

Submission #867567

# Submission time Handle Problem Language Result Execution time Memory
867567 2023-10-28T19:08:54 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;
    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:135:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  135 |     for(int x=1;x<w-1;x++)
      |     ^~~
rect.cpp:140:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  140 |  return res;
      |  ^~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 686872 KB Output is correct
2 Correct 159 ms 689240 KB Output is correct
3 Correct 169 ms 689256 KB Output is correct
4 Correct 158 ms 689384 KB Output is correct
5 Correct 161 ms 689100 KB Output is correct
6 Correct 155 ms 689324 KB Output is correct
7 Correct 164 ms 687188 KB Output is correct
8 Correct 154 ms 689236 KB Output is correct
9 Correct 156 ms 689084 KB Output is correct
10 Correct 158 ms 689240 KB Output is correct
11 Correct 157 ms 689236 KB Output is correct
12 Correct 157 ms 689236 KB Output is correct
13 Correct 153 ms 687052 KB Output is correct
14 Correct 154 ms 686932 KB Output is correct
15 Correct 156 ms 686932 KB Output is correct
16 Correct 161 ms 686932 KB Output is correct
17 Correct 158 ms 687048 KB Output is correct
18 Correct 169 ms 686956 KB Output is correct
19 Correct 156 ms 689060 KB Output is correct
20 Correct 174 ms 687100 KB Output is correct
21 Correct 157 ms 687184 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 686872 KB Output is correct
2 Correct 159 ms 689240 KB Output is correct
3 Correct 169 ms 689256 KB Output is correct
4 Correct 158 ms 689384 KB Output is correct
5 Correct 161 ms 689100 KB Output is correct
6 Correct 155 ms 689324 KB Output is correct
7 Correct 164 ms 687188 KB Output is correct
8 Correct 154 ms 689236 KB Output is correct
9 Correct 156 ms 689084 KB Output is correct
10 Correct 158 ms 689240 KB Output is correct
11 Correct 157 ms 689236 KB Output is correct
12 Correct 157 ms 689236 KB Output is correct
13 Correct 153 ms 687052 KB Output is correct
14 Correct 154 ms 686932 KB Output is correct
15 Correct 156 ms 686932 KB Output is correct
16 Correct 161 ms 686932 KB Output is correct
17 Correct 158 ms 687048 KB Output is correct
18 Correct 169 ms 686956 KB Output is correct
19 Correct 156 ms 689060 KB Output is correct
20 Correct 174 ms 687100 KB Output is correct
21 Correct 157 ms 687184 KB Output is correct
22 Correct 181 ms 690780 KB Output is correct
23 Correct 174 ms 691024 KB Output is correct
24 Correct 176 ms 690956 KB Output is correct
25 Correct 156 ms 689748 KB Output is correct
26 Correct 167 ms 690156 KB Output is correct
27 Correct 163 ms 690080 KB Output is correct
28 Correct 167 ms 690260 KB Output is correct
29 Correct 168 ms 689492 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 686872 KB Output is correct
2 Correct 159 ms 689240 KB Output is correct
3 Correct 169 ms 689256 KB Output is correct
4 Correct 158 ms 689384 KB Output is correct
5 Correct 161 ms 689100 KB Output is correct
6 Correct 155 ms 689324 KB Output is correct
7 Correct 164 ms 687188 KB Output is correct
8 Correct 154 ms 689236 KB Output is correct
9 Correct 156 ms 689084 KB Output is correct
10 Correct 158 ms 689240 KB Output is correct
11 Correct 157 ms 689236 KB Output is correct
12 Correct 157 ms 689236 KB Output is correct
13 Correct 153 ms 687052 KB Output is correct
14 Correct 154 ms 686932 KB Output is correct
15 Correct 156 ms 686932 KB Output is correct
16 Correct 161 ms 686932 KB Output is correct
17 Correct 181 ms 690780 KB Output is correct
18 Correct 174 ms 691024 KB Output is correct
19 Correct 176 ms 690956 KB Output is correct
20 Correct 156 ms 689748 KB Output is correct
21 Correct 167 ms 690156 KB Output is correct
22 Correct 163 ms 690080 KB Output is correct
23 Correct 167 ms 690260 KB Output is correct
24 Correct 168 ms 689492 KB Output is correct
25 Correct 158 ms 687048 KB Output is correct
26 Correct 169 ms 686956 KB Output is correct
27 Correct 156 ms 689060 KB Output is correct
28 Correct 174 ms 687100 KB Output is correct
29 Correct 157 ms 687184 KB Output is correct
30 Correct 508 ms 701412 KB Output is correct
31 Correct 519 ms 701472 KB Output is correct
32 Correct 565 ms 701780 KB Output is correct
33 Correct 188 ms 693296 KB Output is correct
34 Correct 200 ms 696472 KB Output is correct
35 Correct 201 ms 696660 KB Output is correct
36 Correct 203 ms 696144 KB Output is correct
37 Correct 206 ms 696036 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 686872 KB Output is correct
2 Correct 159 ms 689240 KB Output is correct
3 Correct 169 ms 689256 KB Output is correct
4 Correct 158 ms 689384 KB Output is correct
5 Correct 161 ms 689100 KB Output is correct
6 Correct 155 ms 689324 KB Output is correct
7 Correct 164 ms 687188 KB Output is correct
8 Correct 154 ms 689236 KB Output is correct
9 Correct 156 ms 689084 KB Output is correct
10 Correct 158 ms 689240 KB Output is correct
11 Correct 157 ms 689236 KB Output is correct
12 Correct 157 ms 689236 KB Output is correct
13 Correct 153 ms 687052 KB Output is correct
14 Correct 154 ms 686932 KB Output is correct
15 Correct 156 ms 686932 KB Output is correct
16 Correct 161 ms 686932 KB Output is correct
17 Correct 181 ms 690780 KB Output is correct
18 Correct 174 ms 691024 KB Output is correct
19 Correct 176 ms 690956 KB Output is correct
20 Correct 156 ms 689748 KB Output is correct
21 Correct 167 ms 690156 KB Output is correct
22 Correct 163 ms 690080 KB Output is correct
23 Correct 167 ms 690260 KB Output is correct
24 Correct 168 ms 689492 KB Output is correct
25 Correct 508 ms 701412 KB Output is correct
26 Correct 519 ms 701472 KB Output is correct
27 Correct 565 ms 701780 KB Output is correct
28 Correct 188 ms 693296 KB Output is correct
29 Correct 200 ms 696472 KB Output is correct
30 Correct 201 ms 696660 KB Output is correct
31 Correct 203 ms 696144 KB Output is correct
32 Correct 206 ms 696036 KB Output is correct
33 Correct 158 ms 687048 KB Output is correct
34 Correct 169 ms 686956 KB Output is correct
35 Correct 156 ms 689060 KB Output is correct
36 Correct 174 ms 687100 KB Output is correct
37 Correct 157 ms 687184 KB Output is correct
38 Correct 1446 ms 775036 KB Output is correct
39 Correct 1386 ms 750580 KB Output is correct
40 Correct 1490 ms 750556 KB Output is correct
41 Execution timed out 5102 ms 726368 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 711252 KB Output is correct
2 Correct 311 ms 710992 KB Output is correct
3 Correct 158 ms 709688 KB Output is correct
4 Correct 155 ms 686932 KB Output is correct
5 Correct 167 ms 710480 KB Output is correct
6 Correct 166 ms 710652 KB Output is correct
7 Correct 167 ms 710512 KB Output is correct
8 Correct 171 ms 710424 KB Output is correct
9 Correct 170 ms 710480 KB Output is correct
10 Correct 161 ms 710012 KB Output is correct
11 Correct 161 ms 710228 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 687048 KB Output is correct
2 Correct 169 ms 686956 KB Output is correct
3 Correct 156 ms 689060 KB Output is correct
4 Correct 174 ms 687100 KB Output is correct
5 Correct 157 ms 687184 KB Output is correct
6 Correct 158 ms 687060 KB Output is correct
7 Correct 2648 ms 941656 KB Output is correct
8 Runtime error 3261 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 156 ms 686872 KB Output is correct
2 Correct 159 ms 689240 KB Output is correct
3 Correct 169 ms 689256 KB Output is correct
4 Correct 158 ms 689384 KB Output is correct
5 Correct 161 ms 689100 KB Output is correct
6 Correct 155 ms 689324 KB Output is correct
7 Correct 164 ms 687188 KB Output is correct
8 Correct 154 ms 689236 KB Output is correct
9 Correct 156 ms 689084 KB Output is correct
10 Correct 158 ms 689240 KB Output is correct
11 Correct 157 ms 689236 KB Output is correct
12 Correct 157 ms 689236 KB Output is correct
13 Correct 153 ms 687052 KB Output is correct
14 Correct 154 ms 686932 KB Output is correct
15 Correct 156 ms 686932 KB Output is correct
16 Correct 161 ms 686932 KB Output is correct
17 Correct 181 ms 690780 KB Output is correct
18 Correct 174 ms 691024 KB Output is correct
19 Correct 176 ms 690956 KB Output is correct
20 Correct 156 ms 689748 KB Output is correct
21 Correct 167 ms 690156 KB Output is correct
22 Correct 163 ms 690080 KB Output is correct
23 Correct 167 ms 690260 KB Output is correct
24 Correct 168 ms 689492 KB Output is correct
25 Correct 508 ms 701412 KB Output is correct
26 Correct 519 ms 701472 KB Output is correct
27 Correct 565 ms 701780 KB Output is correct
28 Correct 188 ms 693296 KB Output is correct
29 Correct 200 ms 696472 KB Output is correct
30 Correct 201 ms 696660 KB Output is correct
31 Correct 203 ms 696144 KB Output is correct
32 Correct 206 ms 696036 KB Output is correct
33 Correct 1446 ms 775036 KB Output is correct
34 Correct 1386 ms 750580 KB Output is correct
35 Correct 1490 ms 750556 KB Output is correct
36 Execution timed out 5102 ms 726368 KB Time limit exceeded
37 Halted 0 ms 0 KB -