/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 30013; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 100007
#define MAXE 100007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
/// code from USACO examples
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;
int N;
struct TRA {
ll x[2][2];
};
TRA traList[MAXV];
vector<ll> uniqX[2];
bool compFunc(const TRA& v1, const TRA& v2) {
if(v1.x[0][0] != v2.x[0][0])
return v1.x[0][0] < v2.x[0][0];
else if(v1.x[0][1] != v2.x[0][1])
return v1.x[0][1] < v2.x[0][1];
else if(v1.x[1][0] != v2.x[1][0])
return v1.x[1][0] < v2.x[1][0];
else
return v1.x[1][1] < v2.x[1][1];
}
int dp[MAXV][2]; /// max and its rep counts, if the i-th tra is used to form the set
/// ------ Segment Treee --------
int Nseg[2][2];
struct SEGNODE {
int val_m, val_mc;
SEGNODE operator+(SEGNODE b) { /// seg operations
SEGNODE ret;
if(val_m == b.val_m) {
ret.val_m = val_m;
ret.val_mc = (val_mc + b.val_mc) % MOD;
} else {
ret.val_m = max(val_m, b.val_m);
ret.val_mc = (val_m > b.val_m) ? val_mc : b.val_mc;
}
return ret;
}
};
SEGNODE seg[2][600007]; /// max 2e5 unique y, which needs 2^19 for Nseg
void buildSeg(int ln, int v = 1, int l = Nseg[0][0], int r = Nseg[0][1]) {
if(l == r) { // leaf
seg[ln][v] = (SEGNODE) {0, 0};
return;
}
int mid = (l + r) / 2;
buildSeg(ln, 2*v, l, mid); buildSeg(ln, 2*v+1, mid+1, r);
seg[ln][v] = seg[ln][2*v] + seg[ln][2*v+1];
}
void initSeg() {
/// build a segment tree for array of interest indexed from Nseg[0] to Nseg[1]
Nseg[0][0] = 0; Nseg[0][1] = uniqX[0].size();
Nseg[1][0] = 0; Nseg[1][1] = uniqX[1].size();
buildSeg(0,1,Nseg[0][0], Nseg[0][1]);
buildSeg(1,1,Nseg[1][0], Nseg[1][1]);
}
SEGNODE querySeg(int ln, ll qle, ll qri, int v = 1, int l = Nseg[0][0], int r = Nseg[0][1]) {
if(uniqX[ln][r] < qle || uniqX[ln][l] > qri) return {0, 0};
if(qle <= uniqX[ln][l] && uniqX[ln][r] <= qri) return seg[ln][v];
int mid = (l + r) / 2;
return querySeg(ln, qle, qri, 2*v, l, mid) + querySeg(ln, qle, qri, 2*v+1, mid+1, r);
}
void updateSeg(int ln, ll vtx, int v1, int v2, int v = 1, int l = Nseg[0][0], int r = Nseg[0][1]){
if(l == r) { // leaf
seg[ln][v] = (SEGNODE) {v1, v2}; /// dp of max and # of max
return;
}
int mid = (l + r) / 2;
(vtx <= uniqX[ln][mid]) ? updateSeg(ln, vtx, v1, v2, 2*v, l, mid) : updateSeg(ln, vtx, v1, v2, 2*v+1, mid+1, r);
seg[ln][v] = seg[ln][2*v] + seg[ln][2*v+1];
}
int main() {
debug = false; submit = false;
if(submit) setIO("testName");
int i, j, k;
int ans = 0;
cin >> N ;
for(i=1; i<=N; i++) {
cin >> traList[i].x[0][0] >> traList[i].x[0][1] >> traList[i].x[1][0] >> traList[i].x[1][1];
uniqX[0].pb(traList[i].x[0][0]); uniqX[0].pb(traList[i].x[0][1]);
uniqX[1].pb(traList[i].x[1][0]); uniqX[1].pb(traList[i].x[1][1]);
}
traList[0] = {0,0,0,0}; traList[N+1] = {INF, INF, INF, INF};
uniqX[0].pb(0); uniqX[0].pb(INF); uniqX[1].pb(0); uniqX[1].pb(INF);
sort(uniqX[0].begin(), uniqX[0].end()); // uniqX[0].erase(unique(uniqX[0].begin(), uniqX[0].end()), uniqX[0].end());
sort(uniqX[1].begin(), uniqX[1].end()); // uniqX[0].erase(unique(uniqX[0].begin(), uniqX[0].end()), uniqX[0].end());
sort(traList, traList+N+2, compFunc);
dp[0][0] = 0; dp[0][1] = 0;
initSeg();
updateSeg(0, 0, 0, 1, 1, Nseg[0][0], Nseg[0][1]);
updateSeg(1, 0, 0, 1, 1, Nseg[1][0], Nseg[1][1]);
SEGNODE ans1, ans2;
for(i=1; i<=N+1; i++) {
ans1 = querySeg(0, 0, traList[i].x[0][0]-1, 1, Nseg[0][0], Nseg[0][1]);
ans2 = querySeg(1, 0, traList[i].x[1][0]-1, 1, Nseg[1][0], Nseg[1][1]);
if(debug) cout << endl;
if(debug) cout << i << " " << ans1.val_m+1 << " " << ans1.val_mc << endl;
if(debug) cout << i << " " << ans2.val_m+1 << " " << ans2.val_mc << endl;
if(ans1.val_m > ans2.val_m) {
ans1.val_m = ans2.val_m; ans1.val_mc = ans2.val_mc;
}
updateSeg(0, traList[i].x[0][1], ans1.val_m + 1, ans1.val_mc, 1, Nseg[0][0], Nseg[0][1]);
updateSeg(1, traList[i].x[1][1], ans1.val_m + 1, ans1.val_mc, 1, Nseg[1][0], Nseg[1][1]);
if(debug) cout << i << " " << ans1.val_m+1 << " " << ans1.val_mc << endl;
}
cout << ans1.val_m << " " << ans1.val_mc << endl;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:137:12: warning: unused variable 'j' [-Wunused-variable]
137 | int i, j, k;
| ^
trapezoid.cpp:137:15: warning: unused variable 'k' [-Wunused-variable]
137 | int i, j, k;
| ^
trapezoid.cpp:138:9: warning: unused variable 'ans' [-Wunused-variable]
138 | int ans = 0;
| ^~~
trapezoid.cpp: In function 'void setIO(std::string)':
trapezoid.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
52 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
53 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:175:39: warning: 'ans1.SEGNODE::val_mc' may be used uninitialized in this function [-Wmaybe-uninitialized]
175 | cout << ans1.val_m << " " << ans1.val_mc << endl;
| ^~~~~~
trapezoid.cpp:175:27: warning: 'ans1.SEGNODE::val_m' may be used uninitialized in this function [-Wmaybe-uninitialized]
175 | cout << ans1.val_m << " " << ans1.val_mc << endl;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 5 |
Incorrect |
5 ms |
620 KB |
Output isn't correct |
| 6 |
Incorrect |
7 ms |
1004 KB |
Output isn't correct |
| 7 |
Incorrect |
10 ms |
1132 KB |
Output isn't correct |
| 8 |
Incorrect |
13 ms |
1388 KB |
Output isn't correct |
| 9 |
Incorrect |
28 ms |
2408 KB |
Output isn't correct |
| 10 |
Incorrect |
51 ms |
4448 KB |
Output isn't correct |
| 11 |
Incorrect |
68 ms |
4832 KB |
Output isn't correct |
| 12 |
Incorrect |
122 ms |
9176 KB |
Output isn't correct |
| 13 |
Incorrect |
144 ms |
10024 KB |
Output isn't correct |
| 14 |
Incorrect |
180 ms |
15184 KB |
Output isn't correct |
| 15 |
Incorrect |
204 ms |
15592 KB |
Output isn't correct |
| 16 |
Incorrect |
213 ms |
15952 KB |
Output isn't correct |
| 17 |
Incorrect |
226 ms |
16464 KB |
Output isn't correct |
| 18 |
Incorrect |
223 ms |
16848 KB |
Output isn't correct |
| 19 |
Incorrect |
240 ms |
17360 KB |
Output isn't correct |
| 20 |
Incorrect |
260 ms |
17744 KB |
Output isn't correct |
