제출 #874295

#제출 시각아이디문제언어결과실행 시간메모리
874295RequiemExamination (JOI19_examination)C++17
43 / 100
3067 ms666348 KiB
#include<bits/stdc++.h> //#define int long long #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define pb push_back #define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #define MOD 1000000007 #define INF 1e18 #define fi first #define se second #define FOR(i,a,b) for(int i=a;i<=b;i++) #define FORD(i,a,b) for(int i=a;i>=b;i--) #define sz(a) ((int)(a).size()) #define endl '\n' #define all(a) a.begin(),a.end() #define pi 3.14159265359 #define TASKNAME "examination" template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } using namespace std; typedef pair<int,int> ii; typedef pair<int,ii> iii; typedef vector<int> vi; typedef pair<ii,ii> iv; const int MAXN = 1e5+9; const int block = 316; const int MAXBLOCK = 320; int n,q,x,start,b; iv score[MAXN], original[MAXN]; int BIT[330][6*MAXN],nxt[6*MAXN],prep[MAXN],rev[MAXN],cnt[MAXN],answer[MAXN]; vector<int> listval; vector<iv> query; void upd(int block,int id,int x){ for(int i=id;i>0;i-=i&(-i)){ BIT[block][i] += x; } } int get(int block,int id){ int res = 0; for(int i=id;i<=listval.size();i+=i&(-i)){ res += BIT[block][i]; } return res; } int bs(int l,int r,int x){ int res = r+1; while(l<=r){ int mid = (l+r)>>1; if (original[mid].se.fi >= x){ res = mid; r = mid - 1; } else l = mid + 1; } return res; } main() { fast; if (fopen(TASKNAME".inp","r")){ freopen(TASKNAME".inp","r",stdin); freopen(TASKNAME".out","w",stdout); } cin>>n>>q; for(int i=1;i<=n;i++){ cin>>score[i].se.fi>>score[i].se.se; score[i].fi.se = score[i].se.fi + score[i].se.se; listval.pb(score[i].se.fi); listval.pb(score[i].se.se); listval.pb(score[i].fi.se); } sort(score+1,score+1+n,[](const iv &a,const iv &b){ return a.se.fi < b.se.fi; }); for(int i=1;i<=q;i++){ int x,y,z; cin>>x>>y>>z; listval.pb(x); listval.pb(y); listval.pb(z); query.pb({{i,x},{y,z}}); } sort(listval.begin(),listval.end()); listval.erase(unique(listval.begin(),listval.end()),listval.end()); for(int i=1;i<=max(q,n);i++){ if (i<=n){ score[i].se.fi = lower_bound(all(listval),score[i].se.fi) - listval.begin() + 1; score[i].se.se = lower_bound(all(listval),score[i].se.se) - listval.begin() + 1; score[i].fi.se = lower_bound(all(listval),score[i].fi.se) - listval.begin() + 1; } if (i<=q){ query[i-1].se.fi = lower_bound(all(listval),query[i-1].se.fi) - listval.begin() + 1; query[i-1].se.se = lower_bound(all(listval),query[i-1].se.se) - listval.begin() + 1; query[i-1].fi.se = lower_bound(all(listval),query[i-1].fi.se) - listval.begin() + 1; } } for(int i=1;i<=n;i++){ score[i].fi.fi = i; original[i] = score[i]; } int ptr = 1; for(int i=1;i<=listval.size();i++){ while(ptr <= n and original[ptr].se.fi < i){ ptr++; } if (ptr<=n) nxt[i] = original[ptr].fi.fi; else nxt[i] = n+1; } sort(query.begin(),query.end(),[](const iv &a,const iv &b){ return a.se.se > b.se.se; }); sort(score+1,score+1+n,[](const iv &a,const iv &b){ return a.fi.se > b.fi.se; }); for(int i=1;i<MAXN;i++){ prep[i] = i / block; } ptr = 1; for(int i=0;i<query.size();i++){ while(ptr <= n and score[ptr].fi.se >= query[i].se.se){ int RealIndex = score[ptr].fi.fi; rev[RealIndex]++; int b = prep[RealIndex]; cnt[b]++; upd(b,score[ptr].se.se,1); ptr++; } start = nxt[query[i].fi.se]; b = prep[start]; for(int j=start;j<=n;j++){ if (original[j].se.fi >= query[i].fi.se and original[j].se.se >= query[i].se.fi and original[j].fi.se >= query[i].se.se and rev[j] > 0){ answer[query[i].fi.fi]++; } if (prep[j] != prep[j+1]) { break; } } for(int cur=b+1;cur<MAXBLOCK;cur++){ if (cur * block > n) break; if (cnt[cur] == 0) continue; answer[query[i].fi.fi] += get(cur,query[i].se.fi); } } for(int i=1;i<=q;i++){ cout<<answer[i]<<endl; } }

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

examination.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
examination.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
examination.cpp: In function 'int get(int, int)':
examination.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=id;i<=listval.size();i+=i&(-i)){
      |                  ~^~~~~~~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main()
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i=1;i<=listval.size();i++){
      |                 ~^~~~~~~~~~~~~~~~
examination.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i=0;i<query.size();i++){
      |                 ~^~~~~~~~~~~~~
examination.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...