oj.uz

답안 #694972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
694972 2023-02-04T16:04:53 Z Nhoksocqt1 Bob (COCI14_bob) C++17
120 / 120
 605 ms 17816 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

int readInt() {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while(true) {
		if(ch == '-') break;
		if(ch >= '0' && ch <= '9') break;
		ch = getchar();
	}

	if(ch == '-') minus = true; else result = ch - '0';
	while(true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result * 10 + (ch - '0');
	}

	if(minus)
		return -result;
	else
		return result;
}

const int MAXN = 1003;

vector<int> adj1[MAXN], adj2[MAXN], tmp1[MAXN], tmp2[MAXN];
int val[MAXN][MAXN], it1[MAXN], it2[MAXN], row, col;

inline int C2(int n) {
    return n * (n + 1) / 2;
}

void process() {
    cin >> row >> col;
    for (int i = 1; i <= row; ++i) {
        for (int j = 1; j <= col; ++j) {
            cin >> val[i][j];
            if(i > 1 && val[i][j] != val[i - 1][j])
                adj1[i].push_back(j);

            if(j > 1 && val[i][j] != val[i][j - 1])
                adj2[i].push_back(j);
        }
    }

    ll res(0);
    for (int l = 1; l <= col; ++l) {
        for (int r = l; r <= col; ++r)
            tmp1[r].clear(), tmp2[r].clear();

        for (int i = 1; i <= row; ++i) {
            while(it1[i] < int(adj1[i].size()) && adj1[i][it1[i]] < l)
                ++it1[i];

            if(it1[i] < int(adj1[i].size()))
                tmp1[adj1[i][it1[i]]].push_back(i);
        }

        for (int i = 1; i <= row; ++i) {
            while(it2[i] < int(adj2[i].size()) && adj2[i][it2[i]] <= l)
                ++it2[i];

            if(it2[i] < int(adj2[i].size()))
                tmp2[adj2[i][it2[i]]].push_back(i);
        }

        set<ii> line;
        set<int> sz;
        int cnt = C2(row);

        line.insert(ii(row, 1));
        sz.insert(row);
        for (int r = l; r <= col; ++r) {
            for (int jt = 0; jt < int(tmp1[r].size()); ++jt) {
                int x(tmp1[r][jt]);
                auto it = line.lower_bound(ii(x, 1));
                if(it == line.end() || it->se >= x)
                    continue;

                ii tmp = *it;
                line.erase(it);
                sz.erase(tmp.fi - tmp.se + 1);
                cnt -= C2(tmp.fi - tmp.se + 1);

                line.insert(ii(tmp.fi, x));
                line.insert(ii(x - 1, tmp.se));
                sz.insert(tmp.fi - x + 1);
                sz.insert(x - tmp.se);
                cnt += C2(x - tmp.se) + C2(tmp.fi - x + 1);
            }

            for (int jt = 0; jt < int(tmp2[r].size()); ++jt) {
                int x(tmp2[r][jt]);
                auto it = line.lower_bound(ii(x, 1));
                if(it == line.end() || it->se > x)
                    continue;

                ii tmp = *it;
                line.erase(it);
                sz.erase(tmp.fi - tmp.se + 1);
                cnt -= C2(tmp.fi - tmp.se + 1);

                if(tmp.se < x) {
                    line.insert({x - 1, tmp.se});
                    sz.insert(x - tmp.se);
                    cnt += C2(x - tmp.se);
                }

                if(tmp.fi > x) {
                    line.insert({tmp.fi, x + 1});
                    sz.insert(tmp.fi - x);
                    cnt += C2(tmp.fi - x);
                }
            }

            res += cnt;
        }
    }

    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("bob.inp", "r", stdin);
//    freopen("bob.out", "w", stdout);

    process();
    return 0;
}

Compilation message

bob.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
bob.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 4036 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 3760 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 4632 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 4312 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 548 ms 15528 KB Output is correct
2 Correct 213 ms 6356 KB Output is correct
3 Correct 58 ms 6220 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 569 ms 17816 KB Output is correct
2 Correct 314 ms 6832 KB Output is correct
3 Correct 56 ms 6200 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 508 ms 17232 KB Output is correct
2 Correct 55 ms 6288 KB Output is correct
3 Correct 53 ms 6184 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 605 ms 16968 KB Output is correct
2 Correct 64 ms 6220 KB Output is correct
3 Correct 54 ms 6252 KB Output is correct