제출 #938149

#제출 시각아이디문제언어결과실행 시간메모리
938149Lobo자리 배치 (IOI18_seats)C++17
0 / 100
4034 ms258428 KiB
#include "seats.h" #include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() const int maxn = 1e6+10; const int B = 1000; int n, m, col[maxn], row[maxn]; vector<pair<int,int>> mxB[maxn/B+10], mnB[maxn/B+10]; vector<int> vecmxmn[maxn/B+10]; map<int,vector<int>> vecmn[maxn/B+10], vecmx[maxn/B+10]; void construct(int b) { int l = b*B; int r = min(n*m-1,(b+1)*B-1); int mx = -inf; int mn = inf; for(int k = l; k <= r; k++) { if(col[k] > mx) { mx = col[k]; mxB[b].pb(mp(col[k],k)); // crescente } if(col[k] < mn) { mn = col[k]; mnB[b].pb(mp(col[k],k)); // decrescente } if(mx-mn == k) { vecmxmn[b].pb(k); } if(mx-k >= 0 && mx-k < n*m) { vecmx[b][mx-k].pb(k); } if(mn+k >= 0 && mn+k < n*m) { vecmn[b][mn+k].pb(k); } } reverse(all(mnB[b])); // (crescente,decrescente) } int query() { int mx0 = -inf; int mn0 = inf; int ans = 0; for(int b = 0; b*B < n*m; b++) { int l = b*B; int r = min(n*m-1,(b+1)*B-1); auto itmx = upper_bound(all(mxB[b]),mp(mx0,inf)); int posmx; if(itmx != mxB[b].end()) posmx = itmx->sc; else posmx = r+1; auto itmn = upper_bound(all(mnB[b]),mp(mn0,inf)); int posmn; if(itmn != mnB[b].begin()) posmn = prev(itmn)->sc; else posmn = r+1; // depois de mudar os 2 -> max(posmn,posmx) ans+= vecmxmn[b].end() - lower_bound(all(vecmxmn[b]),max(posmn,posmx)); if(posmx < posmn) { // posmx ate posmn-1 // maxk - mn0 = k // maxk - k = mn0 ans+= upper_bound(all(vecmx[b][mn0]),posmn-1) - lower_bound(all(vecmx[b][mn0]),posmx); } else if(posmn < posmx) { ans+= upper_bound(all(vecmn[b][mx0]),posmx-1) - lower_bound(all(vecmn[b][mx0]),posmn); } } return ans; } void give_initial_chart(int32_t H, int32_t W, std::vector<int32_t> R, std::vector<int32_t> C) { n = H; m = W; for(int i = 0; i < n*m; i++) { col[i] = C[i]; row[i] = R[i]; } for(int i = 0; i*B < m; i++) { construct(i); } } int32_t swap_seats(int32_t a, int32_t b) { swap(col[a],col[b]); construct(a/B); construct(b/B); return query(); }

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

seats.cpp: In function 'long long int query()':
seats.cpp:56:7: warning: unused variable 'l' [-Wunused-variable]
   56 |   int l = b*B;
      |       ^
#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...