Submission #131628

#TimeUsernameProblemLanguageResultExecution timeMemory
131628ekremExamination (JOI19_examination)C++98
0 / 100
135 ms30832 KiB
#include <bits/stdc++.h> #define st first #define nd second #define mp make_pair #define pb push_back #define orta ((bas+son)/2) #define mod 1000000007 #define inf 1000000009 #define N 1000005 using namespace std; typedef long long ll; typedef pair < int , int > ii; int n = 1, m = 1, k, q, say1 = 1, say2, seg1[N], sol1[N], sag1[N], seg2[N], sol2[N], sag2[N], ans[N]; pair < int , ii > a[N]; pair < ii , ii > b[N]; int ver(int k){return seg1[k] = (!seg1[k])?++say2:seg1[k];} int solver1(int k){return sol1[k] = (!sol1[k])?++say1:sol1[k];} int sagver1(int k){return sag1[k] = (!sag1[k])?++say1:sag1[k];} int solver2(int k){return sol2[k] = (!sol2[k])?++say2:sol2[k];} int sagver2(int k){return sag2[k] = (!sag2[k])?++say2:sag2[k];} void up2(int k, int bas, int son, int x){ if(bas == son){ seg2[k]++; return; } if(x <= orta) up2(solver2(k), bas, orta, x); else up2(sagver2(k), orta + 1, son, x); seg2[k] = seg2[sol2[k]] + seg2[sag2[k]]; } void up1(int k, int bas, int son, int x, int y){ if(bas == son){ up2(ver(k), 1, m, y); // cout << bas << " " << son << " " << ver(k) << " a " << y << " artti" << endl; return; } if(x <= orta) up1(solver1(k), bas, orta, x, y); else up1(sagver1(k), orta + 1, son, x, y); // cout << bas << " " << son << " " << ver(k) << " a " << y << " artti" << endl; up2(ver(k), 1, m, y); } int qu2(int k, int bas, int son, int x){ if(!k or son < x) return 0; if(bas >= x) return seg2[k]; return qu2(sol2[k], bas, orta, x) + qu2(sag2[k], orta + 1, son, x); } int qu1(int k, int bas, int son, int x, int y){ if(!k or son < x) return 0; if(bas >= x){ // cout << bas << " " << son << " " << seg1[k] << " " << y << " = " << qu2(seg1[k], 1, m, y) << endl; return qu2(seg1[k], 1, m, y); } return qu1(sol1[k], bas, orta, x, y) + qu1(sag1[k], orta + 1, son, x, y); } int main(){ // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d %d",&k ,&q); for(int i = 1; i <= k; i++){ scanf("%d %d",&a[i].nd.st ,&a[i].nd.nd); a[i].st = a[i].nd.st + a[i].nd.nd; n = max(n, a[i].nd.st); m = max(m, a[i].nd.nd); } n++;m++; sort(a + 1, a + k + 1); for(int i = 1; i <= q; i++){ scanf("%d %d %d" ,&b[i].nd.st ,&b[i].nd.nd,&b[i].st.st); b[i].st.nd = i; } sort(b + 1, b + q + 1); reverse(b + 1, b + q + 1); for(int i = 1; i <= q; i++){ while(k >= 1 and a[k].st >= b[i].st.st){ // cout << a[k].nd.st << " " << a[k].nd.nd << " geldi" << endl << endl; up1(1, 1, n, a[k].nd.st, a[k].nd.nd); k--; } // cout << b[i].st.nd << " icin bul " << n << " " << m << endl; ans[b[i].st.nd] = qu1(1, 1, n, min(n, b[i].nd.st), min(m, b[i].nd.nd) ); } for(int i = 1; i <= q; i++) printf("%d\n", ans[i]); return 0; }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&k ,&q);
  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].nd.st ,&a[i].nd.nd);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d" ,&b[i].nd.st ,&b[i].nd.nd,&b[i].st.st);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...