Submission #969894

#TimeUsernameProblemLanguageResultExecution timeMemory
969894VinhLuutrapezoid (balkan11_trapezoid)C++17
80 / 100
90 ms65536 KiB
//#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> //#define int long long #define ll long long #define fi first #define se second #define pb push_back #define all(lmao) lmao.begin(), lmao.end() using namespace std; typedef pair<int,int> pii; typedef tuple<int,int,int> tp; const int N = 1e5 + 5; const int M = 1e6 + 5; const int mod = 30013; //const ll oo = 5e18; int n, a[N], b[N], c[N], d[N], mx = 0; vector<int> open[M], close[M]; int st[M << 1], t[M << 1], f[N], g[N]; void update(int i,int x,int cnt){ i += mx - 1; if(st[i] < x) st[i] = x, t[i] = cnt; else if(st[i] == x) t[i] = (t[i] + cnt) % mod; while(i > 1){ i /= 2; if(st[i] < x) st[i] = x, t[i] = cnt; else if(st[i] == x) t[i] = (t[i] + cnt) % mod; } } pii get(int l,int r){ r++; int ret = 0, cnt = 0; for(l += mx - 1, r += mx - 1; l < r; l /= 2, r /= 2){ if(l & 1){ if(ret < st[l]) ret = st[l], cnt = t[l]; else if(ret == st[l]) cnt = (cnt + t[l]) % mod; l++; } if(r & 1){ --r; if(ret < st[r]) ret = st[r], cnt = t[r]; else if(ret == st[r]) cnt = (cnt + t[r]) % mod; } } return {ret, cnt}; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "v" if(fopen(task ".inp","r")){ freopen(task ".inp","r",stdin); freopen(task ".out","w",stdout); } cin >> n; for(int i = 1; i <= n; i ++){ cin >> a[i] >> b[i] >> c[i] >> d[i]; open[a[i]].pb(i); close[b[i] + 1].pb(i); mx = max({mx, d[i], b[i]}); } for(int i = 1; i <= 1e6; i ++){ for(auto j : close[i]){ update(d[j], f[j], g[j]); // cerr << d[j] << " " << f[j] << " " << g[j] << " up\n"; } for(auto j : open[i]){ auto kq = get(1, c[j] - 1); f[j] = kq.fi + 1, g[j] = kq.se; if(f[j] == 1) g[j] = 1; // cerr << c[j] - 1 << " " << j << " " << f[j] << " " << g[j] << " y\n"; } } int ans = 0, cnt = 0; for(int i = 1; i <= n; i ++) if(ans < f[i]) ans = f[i], cnt = g[i]; else if(ans == f[i]) cnt = (cnt + g[i]) % mod; cout << ans << " " << cnt; }

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...