oj.uz

Submission #156222

# Submission time Handle Problem Language Result Execution time Memory
156222 2019-10-04T14:18:15 Z bvd Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 400192 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define ll long long
using namespace std;
const int maxn = 300010;
const int oo = (int) 1e9;
int n,q;
int s[maxn+1];
int initialS[maxn+1];
string op[maxn+1];
int a[maxn+1],b[maxn+1];
int it[maxn*5],l[maxn*5],r[maxn*5],vt[maxn+1];

vector<int> nodeSet[3][maxn+1];
vector<int> nodes[3][maxn+1];
vector<ll> f[3][maxn+1];

void initIT(int i,int x,int y)
{
	l[i] = x;
	r[i] = y;
	if (x==y)
	{
		it[i] = s[x];
		vt[x] = i;
	}
	else
	{
		int m=(x+y)/2;
		initIT(i*2,x,m);
		initIT(i*2+1,m+1,y);
		it[i] = it[i*2]+it[i*2+1];
	}
}

void updateIT(int i)
{
	if (i==0) return;
	it[i] = it[i*2]+it[i*2+1];
	updateIT(i/2);
}

int getIT(int i,int x,int y)
{
	int res;
	
	if (y<l[i] or x>r[i]) 
		res=0;
	else
	if (x<=l[i] and r[i]<=y)
		res=it[i];
	else
	{
		int res1=getIT(i*2,x,y);
		int res2=getIT(i*2+1,x,y);
		res=res1+res2;
	}
	return res;
}

/**
 * BIT2D Code is from 
 * https://github.com/ngthanhtrung23/ACM_Notebook_new/blob/master/DataStructure/BIT2D.cpp
 */
void fakeUpdate(int id,int u, int v) {
    for(int x = u; x <= n; x += x & -x)
        nodeSet[id][x].push_back(v);
}

void fakeGet(int id,int u, int v) {
    for(int x = u; x > 0; x -= x & -x)
        nodeSet[id][x].push_back(v);
}

void updateBIT(int id,int u,int v,int value) {
    for(int x = u; x <= n; x += x & -x)
        for(int y = lower_bound(nodes[id][x].begin(), nodes[id][x].end(), v) - nodes[id][x].begin(); y < nodes[id][x].size(); y += y & -y)
            f[id][x][y]+=value;
}

ll getBIT(int id,int u,int v) {
    int res = 0;
    for(int x = u; x > 0; x -= x & -x)
        for(int y = lower_bound(nodes[id][x].begin(), nodes[id][x].end(), v) - nodes[id][x].begin(); y > 0; y -= y & -y)
            res += f[id][x][y];
    return res;
}

bool continuous(int x,int y)
{
	return (getIT(1,x,y)==y-x+1);
}

/**
 * fakeGetOnePoint value
 */
void fakeGetOnePoint(int id,int x,int y)
{
	fakeGet(id,x,y);
	fakeGet(id,x-1,y);
	fakeGet(id,x,y-1);
	fakeGet(id,x-1,y-1);
}

int realGetOnePoint(int id,int x,int y)
{
	int a=getBIT(id,x,y);
	int b=getBIT(id,x-1,y);
	int c=getBIT(id,x,y-1);
	int d=getBIT(id,x-1,y-1);
	return a-b-c+d;
}

void fakeClearOneInterval(int leftEndpoint,int rightEndpoint)
{
	fakeGetOnePoint(0,leftEndpoint,rightEndpoint); // get the opening value
	fakeUpdate(0,leftEndpoint,rightEndpoint); // clear the value
	fakeUpdate(1,leftEndpoint,rightEndpoint);
	fakeUpdate(2,leftEndpoint,rightEndpoint); // add to sum 
}

void realClearOneInterval(int leftEndpoint,int rightEndpoint,int currentTime)
{
	int value=realGetOnePoint(0,leftEndpoint,rightEndpoint);
	updateBIT(0,leftEndpoint,rightEndpoint,-value);
	updateBIT(1,leftEndpoint,rightEndpoint,-1);
	updateBIT(2,leftEndpoint,rightEndpoint,currentTime-value);
}

void fakeInsertOneInterval(int leftEndpoint,int rightEndpoint)
{
	fakeUpdate(0,leftEndpoint,rightEndpoint); // open new point
	fakeUpdate(1,leftEndpoint,rightEndpoint); // +1 point in the area
	// 2 is the overall sum
}

void realInsertOneInterval(int leftEndpoint,int rightEndpoint,int currentTime)
{
	updateBIT(0,leftEndpoint,rightEndpoint,currentTime);
	updateBIT(1,leftEndpoint,rightEndpoint,1);
}

void findLeftRight(int currentPosition,int& leftEndpoint,int& rightEndpoint)
{
	// find the old left endpoint
	int dau=0,cuoi=currentPosition-1;
	while (dau<=cuoi)
	{
		int giua=(dau+cuoi)/2;
		if (continuous(giua,currentPosition-1)) cuoi=giua-1;
		else
			dau=giua+1;
	}
	// dau is the result
	
	leftEndpoint = dau;
	
	// find the old right endpoint
	dau=currentPosition+1,cuoi=n;
	while (dau<=cuoi)
	{
		int giua=(dau+cuoi)/2;
		if (continuous(currentPosition+1,giua)) dau=giua+1;
		else
			cuoi=giua-1;
	}
	// cuoi is the result
	
	rightEndpoint = cuoi;
}


void fakeProcess()
{
	for (int i=1; i<=n; i++)
		initialS[i] = s[i];
	
	initIT(1,1,n);
	
	int begin = 0;	
	for (int i=1; i<=n+1; i++)
	{
		if (s[i]==1 and s[i-1]==0)
			begin = i;
		if (s[i]==0 and s[i-1]==1)
			fakeInsertOneInterval(begin,i-1);
	}
	
	for (int i=1; i<=q; i++)
	{
		if (op[i][0]=='t')
		{
			int leftEndpoint,rightEndpoint;
			findLeftRight(a[i],leftEndpoint,rightEndpoint);
			if (s[a[i]]==1)
			{
				fakeClearOneInterval(leftEndpoint,rightEndpoint);
					
				if (leftEndpoint==a[i] and rightEndpoint==a[i])
				{
					// the interval is gone, do nothing
				}
				else
				if (leftEndpoint==a[i])
				{
					leftEndpoint++;
					// add new interval
					fakeInsertOneInterval(leftEndpoint,rightEndpoint);
				}
				else
				if (rightEndpoint==a[i])
				{
					rightEndpoint--;
					// add new interval
					fakeInsertOneInterval(leftEndpoint,rightEndpoint);
				}
				else
				{
					// two new interval
					int leftEndpoint1 = leftEndpoint;
					int rightEndpoint1 = a[i]-1;
					fakeInsertOneInterval(leftEndpoint1,rightEndpoint1);
					int leftEndpoint2 = a[i]+1;
					int rightEndpoint2 = rightEndpoint;
					fakeInsertOneInterval(leftEndpoint2,rightEndpoint2);
				}
			}
			else
			{	
				if (leftEndpoint!=a[i]) // there is a left Interval
					fakeClearOneInterval(leftEndpoint,a[i]-1);
				
				if (rightEndpoint!=a[i])
					fakeClearOneInterval(a[i]+1,rightEndpoint);
					
				fakeInsertOneInterval(leftEndpoint,rightEndpoint);
			}
			
			// update interval tree
			s[a[i]]^=1;
			it[vt[a[i]]] = s[a[i]];
			updateIT(vt[a[i]]/2);
		}
		else
		{
			fakeGet(2,a[i],n);
			fakeGet(2,a[i],b[i]-1);
			fakeGet(1,a[i],n);
			fakeGet(1,a[i],b[i]-1);
			fakeGet(0,a[i],n);
			fakeGet(0,a[i],b[i]-1);
		}
	}
	
	for (int i=1; i<=n; i++)
		s[i] = initialS[i];
}

void initBIT()
{
	fakeProcess();
    
    for (int id=0; id<3; id++)
    { 
		for (int i=1; i<=maxn; i++)
		{
			nodeSet[id][i].push_back(oo);
			nodeSet[id][i].push_back(0);
			sort(nodeSet[id][i].begin(), nodeSet[id][i].end());
			
			for (int j=0; j<nodeSet[id][i].size(); j++)
			{
				if (j==0 or nodeSet[id][i][j]!=nodeSet[id][i][j-1])
					nodes[id][i].push_back(nodeSet[id][i][j]);
			}
			
			
			f[id][i].resize(nodes[id][i].size() + 3);
		}
    }
}

void realProcess()
{
	initIT(1,1,n);
	
	int begin = 0;	
	for (int i=1; i<=n+1; i++)
	{
		if (s[i]==1 and s[i-1]==0)
			begin = i;
		if (s[i]==0 and s[i-1]==1)
			realInsertOneInterval(begin,i-1,0);
	}
	
	for (int i=1; i<=q; i++)
	{
		if (op[i][0]=='t')
		{
			int leftEndpoint,rightEndpoint;
			findLeftRight(a[i],leftEndpoint,rightEndpoint);
			if (s[a[i]]==1)
			{
				realClearOneInterval(leftEndpoint,rightEndpoint,i);
					
				if (leftEndpoint==a[i] and rightEndpoint==a[i])
				{
					// the interval is gone, do nothing
				}
				else
				if (leftEndpoint==a[i])
				{
					leftEndpoint++;
					// add new interval
					realInsertOneInterval(leftEndpoint,rightEndpoint,i);
				}
				else
				if (rightEndpoint==a[i])
				{
					rightEndpoint--;
					// add new interval
					realInsertOneInterval(leftEndpoint,rightEndpoint,i);
				}
				else
				{
					// two new interval
					int leftEndpoint1 = leftEndpoint;
					int rightEndpoint1 = a[i]-1;
					realInsertOneInterval(leftEndpoint1,rightEndpoint1,i);
					int leftEndpoint2 = a[i]+1;
					int rightEndpoint2 = rightEndpoint;
					realInsertOneInterval(leftEndpoint2,rightEndpoint2,i);
				}
			}
			else
			{	
				if (leftEndpoint!=a[i]) // there is a left Interval
					realClearOneInterval(leftEndpoint,a[i]-1,i);
				
				if (rightEndpoint!=a[i])
					realClearOneInterval(a[i]+1,rightEndpoint,i);
					
				realInsertOneInterval(leftEndpoint,rightEndpoint,i);
			}
			
			// update interval tree
			s[a[i]]^=1;
			it[vt[a[i]]] = s[a[i]];
			updateIT(vt[a[i]]/2);
		}
		else
		{
			ll res1 = getBIT(2,a[i],n)-getBIT(2,a[i],b[i]-1); // sum of old intervals
			ll res2 = getBIT(1,a[i],n)-getBIT(1,a[i],b[i]-1); // current number of intervals
			ll res3 = getBIT(0,a[i],n)-getBIT(0,a[i],b[i]-1); // total current starting time of current intervals
			cout << res1+res2*i-res3 << '\n'; 
		}
	}
}


void input()
{
	cin >> n >> q;
	for (int i=1; i<=n; i++)
	{
		char c;
		cin >> c;
		s[i] = c-'0';
	}
	for (int i=1; i<=q; i++)
	{
		cin >> op[i];
		if (op[i][0]=='t')
			cin >> a[i];
		else
		{
			cin >> a[i] >> b[i];
			b[i]--;
		}
	}
}

main()
{
	ios_base::sync_with_stdio(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	input();
	initBIT();
	realProcess();
	
	return 0;
}

Compilation message

street_lamps.cpp: In function 'void updateBIT(int, int, int, int)':
street_lamps.cpp:80:104: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int y = lower_bound(nodes[id][x].begin(), nodes[id][x].end(), v) - nodes[id][x].begin(); y < nodes[id][x].size(); y += y & -y)
                                                                                                      ~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void initBIT()':
street_lamps.cpp:274:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j=0; j<nodeSet[id][i].size(); j++)
                  ~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: At global scope:
street_lamps.cpp:387:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 171896 KB Output is correct
2 Correct 393 ms 171952 KB Output is correct
3 Correct 413 ms 171820 KB Output is correct
4 Correct 405 ms 172068 KB Output is correct
5 Correct 404 ms 171992 KB Output is correct
6 Correct 394 ms 171888 KB Output is correct
7 Correct 393 ms 171896 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1498 ms 212952 KB Output is correct
2 Correct 2013 ms 217736 KB Output is correct
3 Correct 3849 ms 244136 KB Output is correct
4 Execution timed out 5090 ms 364404 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 172496 KB Output is correct
2 Correct 427 ms 172424 KB Output is correct
3 Correct 459 ms 172540 KB Output is correct
4 Correct 402 ms 172248 KB Output is correct
5 Execution timed out 5100 ms 216604 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 172292 KB Output is correct
2 Correct 399 ms 172408 KB Output is correct
3 Correct 402 ms 172384 KB Output is correct
4 Correct 404 ms 172572 KB Output is correct
5 Execution timed out 5065 ms 400192 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 171896 KB Output is correct
2 Correct 393 ms 171952 KB Output is correct
3 Correct 413 ms 171820 KB Output is correct
4 Correct 405 ms 172068 KB Output is correct
5 Correct 404 ms 171992 KB Output is correct
6 Correct 394 ms 171888 KB Output is correct
7 Correct 393 ms 171896 KB Output is correct
8 Correct 1498 ms 212952 KB Output is correct
9 Correct 2013 ms 217736 KB Output is correct
10 Correct 3849 ms 244136 KB Output is correct
11 Execution timed out 5090 ms 364404 KB Time limit exceeded
12 Halted 0 ms 0 KB -