제출 #1137950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137950		henriess	Bitaro the Brave (JOI19_ho_t1)	C++20	0 / 100	0 ms	320 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;
struct node{
	node *left,*right;
	long long S,E,M,val;
	long long lazy;
	node (long long s,long long e):S(s), E(e){
		val = 0;
		left = nullptr;
		right = nullptr;
		lazy = 0;
	}
	void prop(){
		if (S == E){
			return;
		}
		M = (S + E) / 2;
		if (left == nullptr){
			left = new node(S,M);
			right = new node(M+1,E);
		}
		if (lazy != 0){
			left->val += lazy*(M-S+1);
			right->val += lazy*(E-M);
			right->lazy += lazy;
			left->lazy += lazy;
			lazy = 0;
		}
	}
	long long qry(long long l,long long r){
		if (l > E || r < S){
			return 0;
		}
		else if (l <= S && r >= E){
			return val;
		}
		prop();
		return left->qry(l,r) + right->qry(l,r);
	}
	void upd(long long l,long long r,long long v){
		if (l > E || r < S){
			return;
		}
		if (l <= S && E <= r){
			val += v * (E - S + 1);
			lazy += v;
			return;
		}
		prop();
		left->upd(l,r,v);
		right->upd(l,r,v);
		val = left->val + right->val;
	}
}*segtree;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	long long h,w;cin >> h >> w;
	//segment tree stores all valid pairs of O and J for each width, as im going from top to bottom, I dont need to care about the heights
	//line sweep on I
	vector<vector<char>> grid(h,vector<char>(w));
	segtree = new node(0,w-1);
	
	vector<pair<long long,long long>> Ipos;
	for(int i = 0;i<h;i++){
		string s;cin >> s;
		for(int j = 0;j<s.length();j++){
			if (s[j] == 'I'){
				Ipos.push_back({i,j});
			}
			grid[i][j] = s[j];
		}
	}
	vector<vector<long long>> valid(h,vector<long long>(w));
	for(int i = 0;i<h;i++){
		
		long long save=  LLONG_MAX;
		long long numj = 0;
		long long numo = 0;
		for(int j = 0;j<w;j++){
			if (grid[i][j] == 'J'){
				save = j;
				numj += 1;
				
				numo = 0;
				
			}
			if (grid[i][j] == 'O'){
				numo += 1;
				valid[i][save] = numo;
			}
		}
	}
	long long ans = 0;	
	sort(Ipos.rbegin(),Ipos.rend());//sort from top to bottom
	for(int i = 0;i<h;i++){
		for(int j = 0;j<w;j++){
			//cout << valid[i][j] << '\n';
			segtree->upd(j,j,valid[i][j]);
			if (grid[i][j] == 'I'){
				long long r = segtree->qry(j,w-1);
				//cout << r << '\n';
				ans += r;
			}
		}
	}
	
	cout << ans;
		
}

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