제출 #1039717

#제출 시각아이디문제언어결과실행 시간메모리
1039717AndreyGift Exchange (JOI24_ho_t4)C++14
88 / 100
380 ms67924 KiB
#include<bits/stdc++.h> using namespace std; vector<pair<int,int>> haha(100001); vector<int> seg(1000001,-1); vector<int> wow(1000001,-1); vector<pair<int,int>> bruh(100001); vector<pair<int,int>> wut[1000001]; int no; bool yeah = true; void upd(int l, int r, int ql, int qr, int x, int br) { no = max(no,wow[x]); if(l == ql && r == qr) { no = max(no,seg[x]); wow[x] = max(wow[x],br); seg[x] = max(seg[x],wow[x]); return; } int mid = (l+r)/2; if(qr <= mid) { upd(l,mid,ql,qr,x*2,br); } else if(ql > mid) { upd(mid+1,r,ql,qr,x*2+1,br); } else { upd(l,mid,ql,mid,x*2,br); upd(mid+1,r,mid+1,qr,x*2+1,br); } seg[x] = max(wow[x],seg[x*2]); seg[x] = max(seg[x],seg[x*2+1]); } void build(int l, int r, int x) { for(int i = l; i <= r; i++) { wut[x].push_back(bruh[i]); } sort(wut[x].begin(),wut[x].end()); for(int i = 1; i < wut[x].size(); i++) { wut[x][i] = {wut[x][i].first,max(wut[x][i].second,wut[x][i-1].second)}; } if(l == r) { return; } int mid = (l+r)/2; build(l,mid,x*2); build(mid+1,r,x*2+1); } void dude(int l, int r, int ql, int qr, int x, int s, int b) { if(l == ql && r == qr) { if(wut[x][0].first >= s) { return; } int bl = 0,br = wut[x].size()-1; while(bl < br) { int mid = (bl+br+1)/2; if(wut[x][mid].first < s) { bl = mid; } else { br = mid-1; } } if(wut[x][bl].second > b) { yeah = false; } return; } int mid = (l+r)/2; if(qr <= mid) { dude(l,mid,ql,qr,x*2,s,b); } else if(ql > mid) { dude(mid+1,r,ql,qr,x*2+1,s,b); } else { dude(l,mid,ql,mid,x*2,s,b); dude(mid+1,r,mid+1,qr,x*2+1,s,b); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,a,b; cin >> n; for(int i = 1; i <= n; i++) { cin >> a; haha[i] = {0,a}; } for(int i = 1; i <= n; i++) { cin >> a; haha[i] = {a,haha[i].second}; } for(int i = 1; i <= n; i++) { no = -1; upd(1,2*n,haha[i].first,haha[i].second,1,i); bruh[i] = {no,0}; } for(int i = 0; i < seg.size(); i++) { seg[i] = -1; wow[i] = -1; } for(int i = n; i >= 1; i--) { no = -1; upd(1,2*n,haha[i].first,haha[i].second,1,n-i+1); bruh[i] = {bruh[i].first,n-no+1}; } build(1,n,1); int q; cin >> q; for(int i = 0; i < q; i++) { cin >> a >> b; yeah = true; dude(1,n,a,b,1,a,b); if(yeah) { cout << "Yes\n"; } else { cout << "No\n"; } } return 0; }

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

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 1; i < wut[x].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:104:22: 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 = 0; i < seg.size(); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...