Submission #547337

#TimeUsernameProblemLanguageResultExecution timeMemory
547337VictorLand of the Rainbow Gold (APIO17_rainbow)C++17
11 / 100
77 ms18500 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b)-1; i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout << #x << " = " << x << endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; #include "rainbow.h" int dr[] = {1, -1, 0, 0}; int dc[] = {0, 0, 1, -1}; int rows, cols, AR, AC, BR, BC,min_col,max_col; bool yes=0; vii segments[3]; vector<vector<bool>> grid, vis; bool valid(int row, int col) { return AR <= row && row < BR && AC <= col && col < BC; } void dfs(int row, int col) { vis[row][col] = 1; if(yes) { min_col=min(min_col,col); max_col=max(max_col,col); } // cout<<"row = "<<row<<" col = "<<col<<" grid = "<<grid[row][col]<<endl; rep(k, 0, 4) { int nr = row + dr[k], nc = col + dc[k]; if (valid(nr, nc) && !vis[nr][nc] && !grid[nr][nc]) dfs(nr, nc); } } void init(int R, int C, int sr, int sc, int M, char *S) { rows = R; cols = C; --sr; --sc; rep(i, 0, M) { if (S[i] == 'S') S[i] = 0; if (S[i] == 'N') S[i] = 1; if (S[i] == 'E') S[i] = 2; if (S[i] == 'W') S[i] = 3; } if ((rows <= 50 && cols <= 50) || rows == 2) { grid.assign(R, vector<bool>(C, 0)); grid[sr][sc] = 1; rep(i, 0, M) { sr += dr[S[i]]; sc += dc[S[i]]; grid[sr][sc] = 1; } //rep(i,0,rows) { // rep(j,0,cols) cout<<grid[i][j]<<' '; // cout<<endl; // } // cout<<endl; } if (rows == 2) { yes=1; AC=0; BC=cols; rep(k, 0, 3) { segments[k].emplace_back(-1,-1); if(!k) { AR=0; BR=1; } if(k==1) { AR=1; BR=2; } if(k==2) { AR=0; BR=2; } vis.assign(rows, vector<bool>(cols, 0)); rep(i, AR, BR) { rep(j, 0, cols) { if (vis[i][j] || grid[i][j]) continue; min_col=INF; max_col=0; dfs(i, j); segments[k].emplace_back(min_col,max_col); } } } yes=0; } } int colour(int ar, int ac, int br, int bc) { int ans = 0; --ar; --ac; if (rows <= 50 && cols <= 50) { AR = ar; AC = ac; BR = br; BC = bc; vis.assign(rows, vector<bool>(cols, 0)); rep(i, ar, br) { rep(j, ac, bc) { if (vis[i][j] || grid[i][j]) continue; ++ans; dfs(i, j); } } } else if(rows==2) { int k=0; if(br==2) k=2-ar; auto it_left=upper_bound(all(segments[k]),ii(ac,INF)); if(it_left!=segments[k].begin()) { --it_left; //cout<<"it_left = "<<it_left->second<<" ac = "<<ac<<endl; if(it_left->second<ac) ++it_left; } //debug(k); //debug(sz(segments[k])); auto it_right=upper_bound(all(segments[k]),ii(bc,-1)); --it_right; //cout<<"it_right = "<<it_right->first<<' '<<it_right->second<<endl; int lpos=it_left-segments[k].begin(); int rpos=it_right-segments[k].begin(); ans=max(0,rpos-lpos+1); //cout<<lpos<<' '<<rpos<<endl; } return ans; } /* #include <stdio.h> #include "rainbow.h" static int R, C, M, Q; static int sr, sc; static char S[100000 + 5]; int main() { scanf("%d %d %d %d", &R, &C, &M, &Q); scanf("%d %d", &sr, &sc); if (M > 0) { scanf(" %s ", S); } init(R, C, sr, sc, M, S); int query; for (query = 0; query < Q; query++) { int ar, ac, br, bc; scanf("%d %d %d %d", &ar, &ac, &br, &bc); printf("%d\n", colour(ar, ac, br, bc)); } return 0; } */

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:75:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |             sr += dr[S[i]];
      |                      ~~~^
rainbow.cpp:76:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |             sc += dc[S[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...