Submission #887521

#TimeUsernameProblemLanguageResultExecution timeMemory
887521nnhzzztrapezoid (balkan11_trapezoid)C++17
100 / 100
69 ms15492 KiB
/* [Author: Nguyen Ngoc Hung] - From THPT Ngo Gia Tu with Love */ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <locale> #include <map> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <unordered_set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <valarray> #include <vector> #include <cstring> #include <unordered_map> #include <cmath> #include <array> #include <cassert> #include <random> #include <chrono> using namespace std; #define __nnhzzz__ signed main() #define BIT(i,j) (((i)>>(j))&1LL) #define MASK(i) (1LL<<(i)) #define ALL(x) (x).begin(),(x).end() #define SZ(x) (int)(x).size() #define fi first #define se second #define ll long long #define ld long double #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define pii pair<int,int> #define vpii vector<pii> #define vvpii vector<vpii> #define REPDIS(i,be,en,j) for(int i = (be); i<=(en); i+=j) #define REPD(i,be,en) for(int i = (be); i>=(en); i--) #define REP(i,be,en) for(int i = (be); i<=(en); i++) #define endl "\n" #define MP make_pair // #define int ll //-----------------------------------------------------------------------------------------------// int readInt(){ char c; do{ c = getchar(); }while(c!='-' && !isdigit(c)); bool neg = (c=='-'); int res = neg?0:c-'0'; while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0'); return neg?-res:res; } //------------------------------------------------------------------------------------------------// const ll LINF = 1e18; const int INF = 1e9; const int LOG = 20; const int MAXN = 5e5+7; const int N = 1e2+3; const int MOD = 30013; const int BASE = 1e5; const ld EPS = 1e-9; const ld PI = acos(-1); const int OFFSET = 1e3; //------------------------------------------------------------------------------------------------// template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;} template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;} template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; } template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; } //------------------------------------------------------------------------------------------------// /* ---------------------------------------------------------------- END OF TEMPLATE ---------------------------------------------------------------- Nguyen Ngoc Hung - nnhzzz Training for VOI24 gold medal ---------------------------------------------------------------- */ struct Node{ int x,y,u,v; bool operator < (const Node &other) const { return x<other.x; } }; struct FENWICK_TREE{ vi f; int n; void update(int id, int val){ for(; id<=n; id+=id&-id){ f[id] += val; } } int get(int id){ int res = 0; for(; id>0; id-=id&-id){ res += f[id]; } return res; } int get(int l, int r){ return get(r)-get(l-1); } FENWICK_TREE(int _):n(_){ f.resize(n+1); } }; Node a[MAXN]; pii dp[MAXN]; int n; namespace sub1{ void solve(){ int res1 = 0,res2 = 0; REP(i,1,n){ dp[i] = MP(1,1); int dem = 0; REP(j,1,i-1){ if(a[i].x>a[j].y && a[i].u>a[j].v){ ++dem; if(dp[j].fi>=dp[i].fi) dp[i] = MP(dp[j].fi+1,dp[j].se); else if(dp[i].fi==dp[j].fi+1) dp[i].se = (dp[i].se+dp[j].se)%MOD; } } maxi(res1,dp[i].fi); cerr << dem; } REP(i,1,n) if(dp[i].fi==res1) res2 = (res2+dp[i].se)%MOD; cout << res1 << " " << res2; } } namespace sub2{ struct events{ int fi,se,op,id; bool operator < (const events &other) const { return fi<other.fi; } }; int b[MAXN]; pii f[MAXN]; const int BASE = MAXN-7; pii combine(const pii &u, const pii &v){ if(u.fi<v.fi) return v; if(v.fi<u.fi) return u; return MP(u.fi,(u.se+v.se)%MOD); } void update(int id, pii val){ for(; id<=BASE; id+=id&-id) f[id] = combine(f[id],val); } pii get(int id){ pii res = MP(0,1); for(; id>0; id-=id&-id) res = combine(res,f[id]); return res; } void solve(){ vector<events> ev; vi cur; REP(i,1,n){ ev.push_back({a[i].x,a[i].u,-1,i}); ev.push_back({a[i].y,a[i].v,1,i}); cur.push_back(a[i].u); cur.push_back(a[i].v); } sort(ALL(cur)); cur.resize(unique(ALL(cur))-cur.begin()); sort(ALL(ev)); pii res = MP(1,1); REP(i,0,SZ(ev)-1){ int fi = ev[i].fi,se = ev[i].se,op = ev[i].op,id = ev[i].id; int pos = upper_bound(ALL(cur),se)-cur.begin(); if(op==-1){ dp[id] = get(pos); ++dp[id].fi; res = combine(res,dp[id]); }else{ update(pos,dp[id]); } } cout << res.fi << " " << res.se; } // void solve(){ // pii res = MP(1,1); // vpii cur; vi comp; // REP(i,1,n){ // cur.push_back(MP(a[i].x,a[i].u)); // // cur.push_back(MP(a[i].y,a[i].v)); // comp.push_back(a[i].v); // comp.push_back(a[i].u); // } // sort(ALL(cur)); cur.resize(unique(ALL(cur))-cur.begin()); // sort(ALL(comp)); comp.resize(unique(ALL(comp))-comp.begin()); // FENWICK_TREE fen(MAXN-1); // priority_queue<pii,vpii,greater<pii>> heap; // REP(i,1,n){ // heap.push(MP(a[i].y,a[i].v)); // while(SZ(heap)!=0 && heap.top().fi<a[i].x){ // int pos = upper_bound(ALL(comp),heap.top().se)-comp.begin(); // fen.update(pos,1); // heap.pop(); // } // int pos = upper_bound(ALL(comp),a[i].u)-comp.begin(); // b[i] = fen.get(pos); // } // REP(i,1,n){ // int l = b[i]; // int r = upper_bound(ALL(cur),MP(a[i].x,a[i].u))-cur.begin(); // dp[i] = get(l-1); ++dp[i].fi; // update(r,dp[i]); // cout << dp[i].fi << " " << dp[i].se << endl; // maxi(res,dp[i]); // } // res = get(2*n); // cout << res.fi << " " << res.se; // } } void solve(){ n = readInt(); REP(i,1,n){ //cin >> a[i].x >> a[i].y >> a[i].u >> a[i].v; a[i].x = readInt(); a[i].y = readInt(); a[i].u = readInt(); a[i].v = readInt(); } sort(a+1,a+n+1); sub2::solve(); return ; if(n<=5000){ sub1::solve(); return ; } sub2::solve(); } __nnhzzz__{ ios::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); #define task "test" if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } #define task1 "nnhzzz" if(fopen(task1".inp","r")){ freopen(task1".inp","r",stdin); freopen(task1".out","w",stdout); } int test = 1; while(test--){ solve(); } cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n"; return 0; } /** /\_/\ * (= ._.) * / >TL \>AC **/

Compilation message (stderr)

trapezoid.cpp: In function 'void sub2::solve()':
trapezoid.cpp:48:28: warning: unused variable 'first' [-Wunused-variable]
   48 | #define                fi  first
      |                            ^~~~~
trapezoid.cpp:201:8: note: in expansion of macro 'fi'
  201 |    int fi = ev[i].fi,se = ev[i].se,op = ev[i].op,id = ev[i].id;
      |        ^~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:274:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  274 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:275:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  275 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:279:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  279 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:280:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  280 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...