/** * Translated from housedeconstruction_xiaowuc1.cpp into java by Finn Lidbetter * to demonstrate that this problem can be solved in java. * */ import java.util.*; import java.io.*; public class housedeconstruction_xiaowuc1_translated { static long MOD = 998244353; static int getdist(int a, int b, int len) { int r = (int)Math.abs(b-a); if (r int { int r = abs(b-a); return min(r, len-r); }; cin >> len >> n >> m; */ int[] v = new int[n+m]; int[] hp = new int[n+m]; for (int i=0; i> v(n+m); //for(auto& x: v) cin >> x.first >> x.second; //vector toleft(n+m, -1), toright(n+m, -1); //vector st; int[] toleft = new int[n+m]; int[] toright = new int[n+m]; Arrays.fill(toleft, -1); Arrays.fill(toright, -1); Stack st = new Stack<>(); // forward for(int qq = 0; qq < 2; qq++) { for(int i = 0; i < n+m; i++) { if(hp[i] == 'H') st.add(i); else if(st.size()>0) { int curr = st.pop(); //st.pop_back(); toleft[i] = curr; toright[curr] = i; } } } st = new Stack<>(); // backward for(int qq = 0; qq < 2; qq++) { for(int i = n+m-1; i >= 0; i--) { if(hp[i] == 'H') st.push(i); else if(st.size()>0) { //int curr = st.back(); st.pop_back(); int curr = st.pop(); toright[i] = curr; toleft[curr] = i; } } } long dist = 0; //int64_t dist = 0; long ways = 1; for(int i = 0; i < n+m; i++) { if(toleft[i] >= 0) continue; //vector costs; ArrayList costs = new ArrayList<>(); int curr = i; while(toright[curr] >= 0) { int ncurr = toright[curr]; //costs.push_back(getdist(v[curr].first, v[ncurr].first)); costs.add(getdist(v[curr], v[ncurr], len)); curr = ncurr; } //int64_t evendist = 0; long evendist = 0; for(int j = 1; j < costs.size(); j += 2) evendist += costs.get(j); //int64_t odddist = 0; //int64_t bestdist = evendist + odddist; long odddist = 0; long bestdist = evendist + odddist; int numways = 1; for(int j = 0; j < costs.size(); j += 2) { odddist += costs.get(j); evendist -= costs.get(j+1); if(odddist + evendist < bestdist) { bestdist = odddist + evendist; numways = 0; } //numways += (odddist + evendist) == bestdist; if (odddist+evendist == bestdist) { numways++; } } dist += bestdist; //ways = (ways * int64_t(numways)) % MOD; ways = (ways * (long)numways) % MOD; } System.out.println(dist); System.out.println(ways); //cout << dist << "\n"; //cout << ways << "\n"; } }