# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
61872 |
2018-07-27T03:29:08 Z |
Benq |
Adriatic (CEOI13_adriatic) |
C++11 |
|
435 ms |
144600 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 2501;
template<class T, int SZ> struct sums {
T sum[SZ][SZ];
T maxX[SZ+1], maxY[SZ+1];
T minX[SZ+1], minY[SZ+1];
sums () { memset(sum,0,sizeof sum); }
void init() {
F0R(i,SZ+1) minX[i] = minY[i] = SZ;
FOR(i,1,SZ) FOR(j,1,SZ) {
if (sum[i][j]) {
maxX[j] = max(maxX[j],i);
maxY[i] = max(maxY[i],j);
minX[j] = min(minX[j],i);
minY[i] = min(minY[i],j);
}
sum[i][j] += sum[i][j-1]
+sum[i-1][j]-sum[i-1][j-1];
}
FOR(i,1,SZ) {
minY[i] = min(minY[i],minY[i-1]);
minX[i] = min(minX[i],minX[i-1]);
}
FORd(i,1,SZ) {
maxX[i] = max(maxX[i],maxX[i+1]);
maxY[i] = max(maxY[i],maxY[i+1]);
}
}
T get(int X1, int X2, int Y1, int Y2) {
return sum[X2][Y2]-sum[X1-1][Y2]
-sum[X2][Y1-1]+sum[X1-1][Y1-1];
}
};
sums<int,MX> S;
int N;
ll dp[2][MX][MX];
pi p[250001];
void gendp0() {
FORd(i,1,MX) FOR(j,1,MX) { // currently have all points such that x < i or y > j
dp[0][i][j] = S.get(i,MX-1,1,j);
if (!dp[0][i][j]) continue;
dp[0][i][j] += dp[0][max(i,S.maxX[j+1])][min(j,S.minY[i-1])];
}
}
void gendp1() {
FOR(i,1,MX) FORd(j,1,MX) {
dp[1][i][j] = S.get(1,i,j,MX-1);
if (!dp[1][i][j]) continue;
dp[1][i][j] += dp[1][min(i,S.minX[j-1])][max(j,S.maxY[i+1])];
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
F0R(i,N) {
cin >> p[i].f >> p[i].s;
S.sum[p[i].f][p[i].s] ++;
}
S.init();
gendp0();
gendp1();
F0R(i,N) cout << dp[0][p[i].f][p[i].s]+dp[1][p[i].f][p[i].s]+N-3 << "\n";
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
122744 KB |
Output is correct |
2 |
Correct |
155 ms |
122944 KB |
Output is correct |
3 |
Correct |
156 ms |
122944 KB |
Output is correct |
4 |
Correct |
141 ms |
122944 KB |
Output is correct |
5 |
Correct |
190 ms |
122944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
175 ms |
122944 KB |
Output is correct |
2 |
Correct |
180 ms |
123020 KB |
Output is correct |
3 |
Correct |
164 ms |
123260 KB |
Output is correct |
4 |
Correct |
158 ms |
123260 KB |
Output is correct |
5 |
Correct |
185 ms |
123260 KB |
Output is correct |
6 |
Correct |
180 ms |
123260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
123296 KB |
Output is correct |
2 |
Correct |
177 ms |
123424 KB |
Output is correct |
3 |
Correct |
168 ms |
123424 KB |
Output is correct |
4 |
Correct |
162 ms |
123604 KB |
Output is correct |
5 |
Correct |
160 ms |
123624 KB |
Output is correct |
6 |
Correct |
195 ms |
123820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
124160 KB |
Output is correct |
2 |
Correct |
169 ms |
124316 KB |
Output is correct |
3 |
Correct |
208 ms |
124648 KB |
Output is correct |
4 |
Correct |
194 ms |
124724 KB |
Output is correct |
5 |
Correct |
177 ms |
125088 KB |
Output is correct |
6 |
Correct |
211 ms |
125468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
347 ms |
131132 KB |
Output is correct |
2 |
Correct |
385 ms |
133044 KB |
Output is correct |
3 |
Correct |
435 ms |
135416 KB |
Output is correct |
4 |
Correct |
358 ms |
137168 KB |
Output is correct |
5 |
Correct |
375 ms |
139660 KB |
Output is correct |
6 |
Correct |
385 ms |
142108 KB |
Output is correct |
7 |
Correct |
311 ms |
144600 KB |
Output is correct |