Submission #597672

#	Time	Username	Problem	Language	Result	Execution time	Memory
597672		FatihSolak	Rectangles (IOI19_rect)	C++17	18 / 100	5103 ms	320248 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define N 2505
using namespace std;
struct BIT{
	vector<int> bit;
	int n;
	BIT(int size){
		n = size;
		bit.assign(n+5,0);
	}
	void upd(int pos,int val){
		for(++pos;pos<n;pos += pos & -pos){
			bit[pos] += val;
		}
	}
	int get(int pos){
		int ret = 0;
		for(++pos;pos > 0;pos -= pos & -pos){
			ret += bit[pos];
		}
		return ret;
	}
	int get(int l,int r){
		return get(r) - get(l-1);
	}
};
struct SegTree{
	vector<BIT> t;
	int n;
	SegTree(int size){
		n = size + 5;
		t.assign(4*n,BIT(n));
	}
	void upd(int v,int tl,int tr,int l,int r,int val){
		t[v].upd(r,val);
		if(tl == tr)return;
		int tm = (tl + tr)/2;
		if(l <= tm){
			upd(v*2,tl,tm,l,r,val);
		}
		else upd(v*2+1,tm+1,tr,l,r,val);
	}
	int get(int v,int tl,int tr,int l,int r){
		if(tr <= l){
			return t[v].get(r,n-1);
		}
		if(tl > l){
			return 0;
		}
		int tm = (tl + tr)/2;
		return get(v*2,tl,tm,l,r) + get(v*2+1,tm+1,tr,l,r);
	}
	void upd(int l,int r,int val){
		upd(1,0,n-1,l,r,val);
	}
	int get(int l,int r){
		return get(1,0,n-1,l,r);
	}
};
int mp[N][N];
vector<int> pos[N];
vector<int> prepos[N];
vector<pair<int,int>> ranges[N][N];
vector<pair<int,int>> queries[N][N];
long long count_rectangles(vector<vector<int>> a){
	int n = a.size();
	int m = a[0].size();
    long long ans = 0;
	for(int r1 = 1;r1<=n-2;r1++){
        for(int r2 = r1;r2 <= n-2;r2++){
            for(int c1 = 1;c1<=m-2;c1++){
                for(int c2 = c1;c2 <= m-2;c2++){
                    bool ok = 1;
                    for(int i = r1;i<=r2;i++){
                        for(int j = c1;j<=c2;j++){
                            ok &= a[i][j] < min({a[i][c1-1],a[i][c2+1],a[r1-1][j],a[r2+1][j]});
                        }
                    }
                    ans += ok;
                }
            }
        }
    }
	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28