제출 #209195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209195		AryaKnight	Bitaro the Brave (JOI19_ho_t1)	C++14	50 / 100	1093 ms	41848 KiB

joi2019_ho_t1

//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2")  //Enable AVX
#include<bits/stdc++.h>
using namespace std;

#define all(a) begin(a),end(a)
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

void clr(auto &a,int n){
  a.clear();
  a.resize(n);
}

template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
  input>>x.F>>x.S;
  return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}

template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}

template<typename T>
vector<pair<T,int>> getvec(int n){
  vector<pair<T,int>>a(n);
  for(int i=0;i<a.size();i++){
    cin>>a[i].F;
    a[i].S=i;
  }
  return a;
}

const int mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mul(int a,int b){
  return ((a)*1ll*(b))%mod;
}

void add(int &a,int b){
  a+=b;
  if(a>=mod)a-=mod;
}

int sub(int a,int b){
  a-=b;
  if(a<0){
    a+=mod;
  }
  return a;
}

int powz(int a,int b){
  int res=1;
  while(b){
    if(b&1){
      res=mul(res,a);
    }
    b/=2;
    a=mul(a,a);
  }
  return res;
}

const int N=200005;

void solve(){
  int n,m;
  cin>>n>>m;
  vector<string>a(n);
  cin>>a;
  map<int,vi>rw,cl;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(a[i][j]=='O'){
	rw[i].push_back(j);
      }
      if(a[i][j]=='I'){
	cl[j].push_back(i);
      }
    }
  }
  for(int i=0;i<n;i++){
    sort(all(rw[i]));
  }
  for(int i=0;i<m;i++){
    sort(all(cl[i]));
  }
  ll ans=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(a[i][j]=='J'){
	int it=upper_bound(all(rw[i]),j)-rw[i].begin();
	int it2=upper_bound(all(cl[j]),i)-cl[j].begin();
	ans+=(rw[i].size()-it)*1ll*(cl[j].size()-it2);
      }
    }
  }
  cout<<ans;
 
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc=1;
  //cin>>tc;
  for(int _=0;_<tc;_++){
    // cout<<"Case #"<<_+1<<": ";
    solve();
    if(_!=tc-1){
      cout<<'\n';
    }
  }
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50