Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #197 - Thuật toán n.sqrt(n) bài LITES
Ngày: 28-11-2010
Cập nhật: 28-11-2010
Người gửi: hoanhtien1
Ngôn ngữ: C
Xem: 800

Điểm: 4.0/5 (4 Phiếu)


// Distribute n elements into a table of size sqrt(n) x sqrt(n)
// in which row i stores elements i x sqrt(n) to (i+1) x sqrt(n) - 1.
// If a query involves alternating all elementin in row i, just alternate flag statusRow[i].
// Complexity: n + q x sqrt(n)
// Running time on spoj: 4.16
 
#include <string>
#include <iostream>
#include <cmath>
#include <cassert>
#include <string.h>
 
using namespace std;
 
int n, nRow, nCol;
bool statusCell[320][320], statusRow[320];
int startRow[320], onRow[320];
 
void getPos(int i, int &r, int &c) {
	r = i / nCol;
	c = i % nCol;
}
 
void alternateWholeRow(int i) {
	statusRow[i] = !statusRow[i];
}
 
void alternateCell(int i, int j) {
	statusCell[i][j] = !statusCell[i][j];
	if (statusCell[i][j]) ++onRow[i];
	else --onRow[i];
}
 
void alternatePartRow(int i, int l, int r) {	
	for (int j = l; j <= r; ++j) alternateCell(i, j);
}
 
void alternate(int l, int r) {
	int row1, col1, row2, col2;
	getPos(l, row1, col1);
	getPos(r, row2, col2);
 
//	cout << "alternater " << row1 << " " << col1 << " " << row2 << " " << col2 << endl;
 
	if (row1 < row2) {		
		for (int i = row1 + 1; i < row2; ++i) alternateWholeRow(i);	
 
		if (col1 == 0) alternateWholeRow(row1);
		else alternatePartRow(row1, col1, nCol-1);	
 
		if (col2 == nCol-1) alternateWholeRow(row2);
		else alternatePartRow(row2, 0, col2);
	}
	else {
		if (col1 == 0 && col2 == nCol-1) alternateWholeRow(row1);
		else alternatePartRow(row1, col1, col2);
	}
}
 
int getOnWholeRow(int i) {
	if (statusRow[i]) return nCol - onRow[i];
	else return onRow[i];
}
 
int getOnPartRow(int i, int l, int r) {
//	cout << "getOnPartRow " << i << " " << l << " " << r << endl;
	int cnt = 0;
	for (int j = l; j <= r; ++j) {
		if (statusRow[i] != statusCell[i][j]) ++cnt;
	}
	return cnt;
}
 
int count(int l, int r) {
	int row1, col1, row2, col2;
	getPos(l, row1, col1);
	getPos(r, row2, col2);
 
//	cout << "count " << row1 << " " << col1 << " " << row2 << " " << col2 << endl;
 
	int sum = 0;
	if (row1 < row2) {
		for (int i = row1 + 1; i < row2; ++i) sum += getOnWholeRow(i);
 
		if (col1 == 0) sum += getOnWholeRow(row1);
		else sum += getOnPartRow(row1, col1, nCol-1);
 
		if (col2 == nCol-1) sum += getOnWholeRow(row2);
		else sum += getOnPartRow(row2, 0, col2);
	}
	else {
		if (col1 == 0 && col2 == nCol-1) sum += getOnWholeRow(row1);
		else sum += getOnPartRow(row1, col1, col2);
	}
 
	return sum;
}
 
int main() {
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
 
	int q, x, l, r;
	scanf("%d %d", &n, &q);
 
	// prepare table
	nCol = (int)sqrt(n);
	if (nCol * nCol < n) ++nCol;
	assert(nCol * nCol >= n);
 
	nRow = n / nCol;
	if (nRow * nCol < n) ++nRow;
	assert(nRow * nCol >= n);
 
	memset(statusCell, false, sizeof(statusCell));
	memset(statusRow, false, sizeof(statusRow));
 
	startRow[0] = 0;
	for (int i = 1; i <= nRow; ++i) startRow[i] = startRow[i-1] + nCol;
 
	memset(onRow, 0, sizeof(onRow));
 
	// handle query
	while (q--) {
		scanf("%d %d %d", &x, &l, &r);
 
		if (x==0) alternate(l-1, r-1);
		else printf("%d\n", count(l-1, r-1));
 
		/*cout << "table\n";
		for (int i = 0; i < nRow; ++i) {
			cout << "(" << statusRow[i] << "): ";
			for (int j = 0; j < nCol; ++j) cout << statusCell[i][j] << " ";
			cout << ";    on = " << onRow[i] << endl;
		}
		cout << endl;*/
	}
	return 0;
}