DAY-1 mobiles
Mobile phones
PROBLEM
Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S´S matrix with the rows and columns numbered from 0 to S-1. Each square contains a base station. The number of active mobile phones inside a square can change because a phone is moved from a square to another or a phone is switched on or off. At times, each base station reports the change in the number of active phones to the main base station along with the row and the column of the matrix.
Write a program, which receives these reports and answers queries about the current total number of active mobile phones in any rectangle-shaped area.
INPUT AND OUTPUT
The input is read from standard input as integers and the answers to the queries are written to standard output as integers. The input is encoded as follows. Each input comes on a separate line, and consists of one instruction integer and a number of parameter integers according to the following table.
CONSTRAINTS
Out of the 20 inputs, 16 are such that the table size is at most 512×512.
NOTE: The web test facility feeds your input file to your program’s standard input.
SOLUTION
挺经典的一道数据结构。简单模拟肯定会挂，估计过一两个，但没试过；如果只对x维护二分树结构（我第一次就是这么做的），时间复杂度为O(nlogn)，能过6个点；只有对x和y都维护二分树结构才能AC。很郁闷的是我用的虚BST又比标程的树状数组慢。我的时间消耗（这个评测系统ms不支持卡空间）：
Problem: F:\My Documents\My CPP Files\Other\mobile\test\data\mobile.ini
mobiles_1.in = 5.0 (0.02s)
mobiles_2.in = 5.0 (0.03s)
mobiles_3.in = 5.0 (0.02s)
mobiles_4.in = 5.0 (0.09s)
mobiles_5.in = 5.0 (0.25s)
mobiles_6.in = 5.0 (0.14s)
mobiles_7.in = 5.0 (0.28s)
mobiles_8.in = 5.0 (0.41s)
mobiles_9.in = 5.0 (0.55s)
mobiles_10.in = 5.0 (0.55s)
mobiles_11.in = 5.0 (0.53s)
mobiles_12.in = 5.0 (0.56s)
mobiles_13.in = 5.0 (0.59s)
mobiles_14.in = 5.0 (0.58s)
mobiles_15.in = 5.0 (0.59s)
mobiles_16.in = 5.0 (0.59s)
mobiles_17.in = 5.0 (0.63s)
mobiles_18.in = 5.0 (0.64s)
mobiles_19.in = 5.0 (0.66s)
mobiles_20.in = 5.0 (0.67s)Score = 100.0
TimeUsed = 8.38
AllScore = 100.0Summary:
UserID = tomtung_modifiedScore = 100.0/100.0
TimeUsed = 8.38
双重嵌套虚BST代码：
/*
PROG: mobiles
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#define FILE_IO
using namespace std;
#ifdef FILE_IO
FILE *fin = fopen("mobiles.in","r"),
*fout = fopen("mobiles.out","w");
#else
FILE *fin = stdin, *fout=stdout;
#endif
long S,Less[1024][1024];
long num[1024][1024];//This array is useful when debugging,
//but doesn't affect the output
void Increase(long x, long y, long A){
long lx=0,rx=S-1,nowx;
while(1){
nowx=((lx+rx)>>1);
if(x<=nowx){
long ly=0,ry=S-1,nowy;
while(1){
nowy=((ly+ry)>>1);
if(y<=nowy) Less[nowx][nowy]+=A;
if(y==nowy) break;
else if(y<nowy) ry=nowy-1;
else ly=nowy+1;
}
}
if(x==nowx) break;
else if(x<nowx) rx=nowx-1;
else lx=nowx+1;
}
}
long Sum(long x, long y){
if(x<0||y<0) return 0;
long ans=0;
long lx=0,rx=S-1,nowx;
while(1){
nowx=((lx+rx)>>1);
if(x>=nowx){
long ly=0,ry=S-1,nowy;
while(1){
nowy=((ly+ry)>>1);
if(y>=nowy) ans+=Less[nowx][nowy];
if(y==nowy) break;
else if(y<nowy) ry=nowy-1;
else ly=nowy+1;
}
}
if(x==nowx) return ans;
else if(x<nowx) rx=nowx-1;
else lx=nowx+1;
}
}
/*
void output_array(void){
cout << "nums:" << endl;
for(int i=0;i<S;i++){
for(int j=0;j<S;j++)
cout << num[i][j];
cout << endl;
}
cout << endl;
/*
cout << "less:" << endl;
for(int i=0;i<S;i++){
for(int j=0;j<S;j++)
cout << Less[i][j];
cout << endl;/
cout << "line_sum:" << endl;
for(int i=0;i<S;i++){
for(int j=0;j<S;j++)
cout << line_sum(i,j);
cout << endl;
}
cout <<endl << "------------------------------------------------" << endl;
}
*/
int main()
{
long i,p1,p2,p3,p4;
while(1){
fscanf(fin,"%ld ",&i);
//cout << i << ' ';
switch(i){
case 0:
fscanf(fin,"%ld\n",&S);
//cout << S << endl;
break;
case 1:
fscanf(fin,"%ld %ld %ld\n",&p1,&p2,&p3);
//cout << p1 << ' ' << p2 << ' ' << p3 << endl;
Increase(p1,p2,p3);
break;
case 2:
fscanf(fin,"%ld %ld %ld %ld\n",&p1,&p2,&p3,&p4);
//cout << p1 << ' ' << p2 << ' ' << p3 << ' ' << p4 << endl;
fprintf(fout,"%ld\n",Sum(p3,p4)-Sum(p3,p2-1)-Sum(p1-1,p4)+Sum(p1-1,p2-1));
break;
case 3:
goto outloop;
}
//cout << endl;output_array();
}
outloop:
fflush (fout);
fclose(fin);
fclose(fout);
return 0;
}
最近评论