제출 #344138

#제출 시각아이디문제언어결과실행 시간메모리
344138pure_mem사다리꼴 (balkan11_trapezoid)C++14
0 / 100
1 ms512 KiB
#include <bits/stdc++.h> #define X first #define Y second #define MP make_pair #define ll long long using namespace std; const int N = 1e5 + 1; const int mod = 30013; pair<int, int> t[N * 8], dp[N]; void upd(int v, int tl, int tr, int pos, pair<int, int> val){ if(tl > pos || pos > tr) return; if(tl == tr) return void(t[v] = val); int tm = (tl + tr) / 2; upd(v * 2, tl, tm, pos, val); upd(v * 2 + 1, tm + 1, tr, pos, val); if(t[v * 2].X > t[v * 2 + 1].X) t[v] = t[v * 2]; else if(t[v * 2].X < t[v * 2 + 1].X) t[v] = t[v * 2 + 1]; else t[v] = MP(t[v * 2].X, (t[v * 2].Y + t[v * 2 + 1].Y) % mod); } pair<int, int> get(int v, int tl, int tr, int l, int r){ if(tl > r || l > tr) return MP(0, 0); if(tl >= l && tr <= r) return t[v]; int tm = (tl + tr) / 2; pair<int, int> left = get(v * 2, tl, tm, l, r), right = get(v * 2 + 1, tm + 1, tr, l, r); if(left.X > right.X) return left; else if(left.X < right.X) return right; else return MP(left.X, (left.Y + right.Y) % mod); } int a[4][N], n, m; void shrink(){ vector< pair< int, pair<int, int> > > tmp; scanf("%d", &n); for(int i = 1;i <= n;i++) for(int j = 0;j < 4;j++){ scanf("%d", &a[j][i]); if(j > 1) tmp.push_back(MP(a[j][i], MP(j, i))); } sort(tmp.begin(), tmp.end()); for(int i = 0;i < 2 * n;i++){ if(i == 0 || tmp[i - 1].X != tmp[i].X) m++; a[tmp[i].Y.X][tmp[i].Y.Y] = m; } } int main () { freopen("trapezoid.in", "r", stdin); freopen("trapezoid.out", "w", stdout); shrink(); vector<int> tmp; int len = 0, ans = 0; for(int i = 1;i <= n;i++) tmp.push_back(i), tmp.push_back(-i); sort(tmp.begin(), tmp.end(), [](int x, int y){ x = x > 0?a[1][x]:a[0][-x]; y = y > 0?a[1][y]:a[0][-y]; return x < y; }); for(int v: tmp){ if(v < 0){ v = -v; dp[v] = get(1, 1, m, 1, a[2][v]); dp[v].X += 1; if(dp[v].X == 1) dp[v].Y += 1; if(dp[v].X > len) len = dp[v].X, ans = dp[v].Y; else if(dp[v].X == len) ans = (ans + dp[v].Y) % mod; } else{ upd(1, 1, m, a[3][v], dp[v]); } } printf("%d %d", len, ans); }

컴파일 시 표준 에러 (stderr) 메시지

trapezoid.cpp: In function 'void shrink()':
trapezoid.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
trapezoid.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |    scanf("%d", &a[j][i]);
      |    ~~~~~^~~~~~~~~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:62:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   62 |  freopen("trapezoid.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:63:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  freopen("trapezoid.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...