| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 143606 |
2019-08-14T18:04:14 Z |
Kanon |
Rectangles (IOI19_rect) |
C++14 |
|
7 ms |
1588 KB |
#include <bits/stdc++.h>
using namespace std;
#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)
struct sp {
vector<int> st;
unordered_set<int> alive;
sp(){};
void add(int ss) {
st.push_back(ss);
alive.insert(ss);
}
int pos(int ss) {
return upper_bound(st.begin(), st.end(), ss, greater<int>()) - st.begin();
}
sp operator ^ (const sp &a) const {
sp res;
for(auto i : (a.st.size() < st.size() ? a.st : st)) {
if((a.st.size() < st.size() ? alive : a.alive).count(i)) res.add(i);
}
return res;
}
};
long long count_rectangles(vector<vector<int>> a) {
int m = a.front().size();
int n = a.size();
auto pos = [&] (vector<int> cur) {
int s = cur.size();
vector<pair<int, int>> res;
vector<int> st;
range(i, 0, s) {
while(st.size() && cur[st.back()] <= cur[i]) {
if(st.back() < i - 1) res.emplace_back(st.back() + 1, i - 1);
st.pop_back();
}
if(st.size() && st.back() < i - 1) res.emplace_back(st.back() + 1, i - 1);
st.push_back(i);
}
return res;
};
vector<vector<sp>> cur(n, vector<sp>(m));
range(i, 0, n) {
vector<pair<int, int>> ss = pos(a[i]);
for(auto j : ss) {
cur[i][j.second].add(j.first);
}
}
long long res = 0;
vector<vector<pair<int, int>>> to(n, vector<pair<int, int>> (n, make_pair(-2, -2)));
range(i, 0, m) {
vector<int> psy(n);
range(j, 0, n) psy[j] = a[j][i];
vector<pair<int, int>> ss = pos(psy);
int sz = ss.size();
vector<sp> dp(sz);
vector<int> pr(n, -1);
range(j, 0, sz) {
int p = ss[j].second;
dp[j] = cur[p][i];
while(p >= ss[j].first) {
if(~pr[p]) {
dp[j] = dp[j] ^ dp[pr[p]];
p = ss[pr[p]].first - 1;
} else {
dp[j] = dp[j] ^ cur[p][i];
p--;
}
}
pr[ss[j].second] = j;
int l = to[ss[j].first][ss[j].second].second == i - 1 ? to[ss[j].first][ss[j].second].first : i;
if(l == i) to[ss[j].first][ss[j].second] = make_pair(i, i);
to[ss[j].first][ss[j].second].second = i;
res += dp[j].pos(l);
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
380 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
380 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
380 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
380 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1588 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1360 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1460 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1464 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1460 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1460 KB |
Output is correct |
| 9 |
Incorrect |
6 ms |
1588 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
380 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
