Submission #404282

#TimeUsernameProblemLanguageResultExecution timeMemory
404282AriaHExamination (JOI19_examination)C++11
100 / 100
718 ms93228 KiB
/** I can do this all day **/ #pragma GCC optimize("O2") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define all(x) (x).begin(),(x).end() #define F first #define S second #define Mp make_pair #define SZ(x) (int)x.size() #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout); const int N = 1e5 + 10; const ll mod = 1e9 + 7; const ll mod2 = 998244353; const ll inf = 8e18; const int LOG = 18; ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); } int n; struct segment { int A[N]; vector < int > seg[N << 2], I[N << 2]; void Set(int id, int x) { A[id] = x; } void Merge(int v) { int i = 0, j = 0, n1 = SZ(seg[v << 1]), m = SZ(seg[v << 1 | 1]); I[v].push_back(0); while(i < n1 || j < m) { if(i < n1 && (j == m || seg[v << 1][i] < seg[v << 1 | 1][j])) { seg[v].push_back(seg[v << 1][i ++]); I[v].push_back(I[v].back() + 1); } else { seg[v].push_back(seg[v << 1 | 1][j ++]); I[v].push_back(I[v].back()); } } } void build(int v = 1, int tl = 1, int tr = n) { if(tl == tr) { seg[v].push_back(A[tl]); return; } int mid = (tl + tr) >> 1; build(v << 1, tl, mid); build(v << 1 | 1, mid + 1, tr); Merge(v); } int G(int l, int r, int id, int v = 1, int tl = 1, int tr = n) { if(l > tr || r < tl || l > r) return 0; if(l <= tl && tr <= r) { return id; } int mid = (tl + tr) >> 1; return G(l, r, I[v][id], v << 1, tl, mid) + G(l, r, id - I[v][id], v << 1 | 1, mid + 1, tr); } int get(int l, int r, int x) /// tedad adad l, r, ke A[i] < x { int id = lower_bound(all(seg[1]), x) - seg[1].begin(); return G(l, r, id); } }; int q, ord[N], S[N], T[N], A[N], B[N], C[N]; bool cmp(int i, int j) { return S[i] + T[i] < S[j] + T[j]; } int main() { scanf("%d%d", &n, &q); for(int i = 1; i <= n; i ++) { scanf("%d%d", &S[i], &T[i]); ord[i] = i; } for(int i = 1; i <= q; i ++) { scanf("%d%d%d", &A[i], &B[i], &C[i]); C[i] = max(C[i], A[i] + B[i]); } sort(ord + 1, ord + n + 1, cmp); segment segS, segT; vector < int > vec; for(int i = 1; i <= n; i ++) { ///printf("i = %d ord = %d fir = %d sec = %d\n", i, ord[i], S[ord[i]], T[ord[i]]); segS.Set(i, S[ord[i]]); segT.Set(i, T[ord[i]]); vec.push_back(S[ord[i]] + T[ord[i]]); } segS.build(); segT.build(); for(int i = 1; i <= q; i ++) { int id = lower_bound(all(vec), C[i]) - vec.begin() + 1; ///printf("i = %d id = %d A : %d B : %d\n", i, id, segS.get(id, n, A[i]), segT.get(id, n, B[i])); printf("%d\n", n - id + 1 - segS.get(id, n, A[i]) - segT.get(id, n, B[i])); } return 0; } /** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d%d", &S[i], &T[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf("%d%d%d", &A[i], &B[i], &C[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...