oj.uz

Submission #291130

# Submission time Handle Problem Language Result Execution time Memory
291130 2020-09-04T17:39:50 Z thebes Rectangles (IOI19_rect) C++14
0 / 100
 5000 ms 406200 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define F first
#define S second

const int MN = 2505, MM = 13e6;
int N, M, C, i, j, x, y, h[MM], hp[MM], cnt, pre[MN], nxt[MN]; ll ans;
pii bnd[MM]; vi vec[MN], adj[MM], hid[MN]; set<int> go;
map<pii,int> id; queue<pii> q[MN];
vector<pii> evt[MN]; map<pii,int> hist, tmp;

inline void add(int l,int r,int pid,int x,bool col){
    if(l!=-1&&r!=-1&&!id.count({l,r})){
        if(col){
            id[{l,r}]=1;
            evt[r-1].push_back({x,l+1});
        }
        else{
            id[{l,r}]=++cnt;
            bnd[cnt] = {l+1,r-1};
            h[cnt] = x;
            if(pid!=-1){
                adj[cnt].push_back(pid);
                hp[pid] = 1;
            }
        }
        q[r-l].push({l,r});
    }
}

inline void process(vi vec,int x,bool col){
    C = (int)vec.size();
    map<int,int> mp;
    for(int i=C-1;i>=0;i--){
        auto it=mp.upper_bound(vec[i]);
        if(it==mp.end()) nxt[i]=-1;
        else nxt[i]=it->S;
        while(mp.size()&&mp.begin()->F<=vec[i]) mp.erase(mp.begin());
        mp[vec[i]]=i;
    }
    mp.clear();
    for(int i=0;i<C;i++){
        auto it=mp.upper_bound(vec[i]);
        if(it==mp.end()) pre[i]=-1;
        else pre[i]=it->S;
        while(mp.size()&&mp.begin()->F<=vec[i]) mp.erase(mp.begin());
        mp[vec[i]]=i;
    }
    id.clear();
    queue<pii> hm; vector<pii> tmp;
    for(int i=1;i<C-1;i++){
        int l = pre[i], r = nxt[i];
        if(l!=-1&&r!=-1) tmp.push_back({l,r});
    }
    sort(tmp.begin(),tmp.end(),[](pii i,pii j){return i.S-i.F<j.S-j.F;});
    for(auto v : tmp) hm.push(v);
    tmp.clear();
    for(int i=0;i<=C;i++){
        while(hm.size()&&hm.front().S-hm.front().F==i){
            add(hm.front().F,hm.front().S,-1,x,col);
            hm.pop();
        }
        while(q[i].size()){
            pii cur = q[i].front(); q[i].pop();
            int l, r;
            if(vec[cur.F]==vec[cur.S]) l = pre[cur.F], r = nxt[cur.S];
            else if(vec[cur.F]<vec[cur.S]) l = pre[cur.F], r = cur.S;
            else l = cur.F, r = nxt[cur.S];
            add(l,r,id[cur],x,col);
        }
    }
}

inline void mrg(int x,int y){
    if(x^y){
        vi res;
        for(int i=0,j=0;i<(int)vec[x].size();i++){
            while(j+1<(int)vec[y].size()&&vec[y][j]<vec[x][i]) j++;
            if(j<vec[y].size()&&vec[x][i]==vec[y][j]) res.push_back(vec[x][i]);
        }
        vec[x].clear();
        vec[y]=res;
    }
}

void dfs(int n){
    for(auto v : adj[n]){
        dfs(v);
        mrg(bnd[v].S,bnd[n].S);
    }
    auto it=go.lower_bound(bnd[n].F);
    while(it!=go.end()&&*it<=bnd[n].S){
        mrg(*it,bnd[n].S);
        auto it2=it; it++;
        go.erase(it2);
    }
    int p = upper_bound(vec[bnd[n].S].begin(),vec[bnd[n].S].end(),h[n])-vec[bnd[n].S].begin();
    ans += vec[bnd[n].S].size()-p;
}

long long count_rectangles(vector<vector<int>> a){
	vi col;
	N = a.size(), M = a[0].size();
	for(i=0;i<M;i++){
        col.clear();
        for(j=0;j<N;j++) col.push_back(a[j][i]);
        process(col,i,1);
	}
	for(i=0;i<N;i++)
        process(a[i],i,0);
	for(i=1;i<=cnt;i++){
        hid[h[i]].push_back(i);
	}
	for(i=0;i<N;i++){
        for(j=0;j<M;j++) vec[j].clear(), go.insert(j);
        for(auto v : evt[i]) vec[v.F].push_back(v.S);
        for(j=0;j<M;j++) sort(vec[j].begin(),vec[j].end());
        tmp.clear();
        for(auto v : hid[i]){
            h[v] = hist[bnd[v]]+1;
            tmp[bnd[v]] = h[v];
            h[v] = i-h[v];
        }
        for(auto v : hid[i]){
            if(hp[v]) continue;
            dfs(v);
        }
        swap(hist, tmp);
	}
	return ans;
}

Compilation message

rect.cpp: In function 'void mrg(int, int)':
rect.cpp:84:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             if(j<vec[y].size()&&vec[x][i]==vec[y][j]) res.push_back(vec[x][i]);
      |                ~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 307536 KB Output is correct
2 Correct 200 ms 307576 KB Output is correct
3 Correct 203 ms 307576 KB Output is correct
4 Correct 205 ms 307576 KB Output is correct
5 Correct 208 ms 307448 KB Output is correct
6 Incorrect 192 ms 307576 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 307536 KB Output is correct
2 Correct 200 ms 307576 KB Output is correct
3 Correct 203 ms 307576 KB Output is correct
4 Correct 205 ms 307576 KB Output is correct
5 Correct 208 ms 307448 KB Output is correct
6 Incorrect 192 ms 307576 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 307536 KB Output is correct
2 Correct 200 ms 307576 KB Output is correct
3 Correct 203 ms 307576 KB Output is correct
4 Correct 205 ms 307576 KB Output is correct
5 Correct 208 ms 307448 KB Output is correct
6 Incorrect 192 ms 307576 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 307536 KB Output is correct
2 Correct 200 ms 307576 KB Output is correct
3 Correct 203 ms 307576 KB Output is correct
4 Correct 205 ms 307576 KB Output is correct
5 Correct 208 ms 307448 KB Output is correct
6 Incorrect 192 ms 307576 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 308856 KB Output is correct
2 Correct 220 ms 308692 KB Output is correct
3 Correct 224 ms 307704 KB Output is correct
4 Correct 202 ms 307448 KB Output is correct
5 Incorrect 218 ms 308600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 307448 KB Output is correct
2 Correct 2567 ms 353660 KB Output is correct
3 Execution timed out 5078 ms 406200 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 307536 KB Output is correct
2 Correct 200 ms 307576 KB Output is correct
3 Correct 203 ms 307576 KB Output is correct
4 Correct 205 ms 307576 KB Output is correct
5 Correct 208 ms 307448 KB Output is correct
6 Incorrect 192 ms 307576 KB Output isn't correct
7 Halted 0 ms 0 KB -