oj.uz

Submission #74137

# Submission time Handle Problem Language Result Execution time Memory
74137 2018-08-30T09:23:30 Z haitun Election (BOI18_election) C++14
28 / 100
 3000 ms 1804 KB 
#include <bits/stdc++.h>
//#include "functions.h"
#define FOR(x,y) for(int x = 0; x < y; x++)
#define ALLR(x) x.begin(),x.end()
#define con continue
#define ll long long
#define LINF LLONG_MAX
#define INF INT_MAX
#define pii pair<int,int>
#define vi vector <int>
#define pb push_back
#define F first
#define S second
#define len(x) x.length()
#define sz(x) x.size()
#define SEE(v)	for(auto x : v)	cout << x << " "; cout << endl;
using namespace std;
class BiTree{
	public:
		vector <int> bi;
		int n;
		BiTree(int size){
			for(int j = 0; j <= size; j++)	bi.push_back(0);
			n = size;
		}
		
		void update(int index, int value){
			index++;
			while(index <= n)
			{
				bi[index] += value;
				index += (index & -index);
			}
		}

		int getSum(int index){
			index++;
			int sum = 0;

			while(index > 0)
			{
				sum += bi[index];
				index -= (index & -index);
			}
			return sum;
		}
		
		int rangeSum(int included_start,int included_end){
			if(included_start < 1)	return getSum(included_end);
			else					return getSum(included_end) - getSum(included_start - 1);
		}
		
};
int main(){
	
	if(fopen("test.txt","r"))	freopen("test.txt","r",stdin);
	
	int n;
	cin >> n;
	string s;
	cin >> s;
	
	int q;
	cin >> q;
	vector <pii> sc(q);
	FOR(j, q)	cin >> sc[j].F >> sc[j].S;
	
	BiTree b(n);
	FOR(j, n)
	{
		if(s[j] == 'C')	b.update(j, 1);
		else			b.update(j, 0);
	}
	
	FOR(j, q)
	{
		int l = sc[j].F, r = sc[j].S;
		int size = r - l + 1;
		vector <bool> nulled(size, false);
		
		/*for(int k = l - 1; k < r; k++)
		{
			if(s[k] == 'C')	t.update(k - l + 1, 1);
			else			t.update(k - l + 1, 0);
		}*/
		
		int toner = 0;
		
		FOR(k, size)
		{
			int sum = b.getSum(l - 1 + k) - ((l == 0) ? 0 : b.getSum(l - 2));
			//cout << sum << " ";
			//cout << sum << " " << (k - toner + 1) / 2 + helper << endl;
			if(sum * 2 < k + 1 - toner)
			{
				nulled[k] = true;
				toner++;
				//cout << k << " is updated.\n";
			}
		}
		
		//look from back
		reverse(ALLR(nulled));
		
		
		//FOR(k, nulled.size())	cout << nulled[k] << " ";
		//cout << endl;
		
		/*int k2 = 0;
		for(int k = r - 1; k > l - 2; k--)
		{
			if(s[k] == 'C')	t2.update(k2, 1);
			else			t2.update(k2, 0);
			k2++;
			//cout << s[k] << " ";
		}
		//cout << endl;
		*/
		
		toner = 0;
		
		FOR(k, size)
		{
			int sum = b.getSum(r - 1) - b.getSum(r - k - 2);
			//cout << sum << " ";
			
			if(nulled[k])
			{
				toner++;
				con;
			}
			
			if(sum * 2 < k - toner + 1)
			{
				nulled[k] = true;
				toner++;
				//cout << k << " is updated.\n";
			}
		}
		//cout << endl;
		//return 0;
		int ans = 0;
		
		FOR(k, nulled.size())
		{
			if(nulled[k])	ans++;
		}
		cout << ans << endl;
	}
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:3:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(x,y) for(int x = 0; x < y; x++)
election.cpp:144:7:
   FOR(k, nulled.size())
       ~~~~~~~~~~~~~~~~             
election.cpp:144:3: note: in expansion of macro 'FOR'
   FOR(k, nulled.size())
   ^~~
election.cpp:56:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  if(fopen("test.txt","r")) freopen("test.txt","r",stdin);
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 376 KB Output is correct
2 Correct 39 ms 512 KB Output is correct
3 Correct 36 ms 512 KB Output is correct
4 Correct 47 ms 512 KB Output is correct
5 Correct 41 ms 564 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 376 KB Output is correct
2 Correct 39 ms 512 KB Output is correct
3 Correct 36 ms 512 KB Output is correct
4 Correct 47 ms 512 KB Output is correct
5 Correct 41 ms 564 KB Output is correct
6 Execution timed out 3053 ms 1804 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 376 KB Output is correct
2 Correct 39 ms 512 KB Output is correct
3 Correct 36 ms 512 KB Output is correct
4 Correct 47 ms 512 KB Output is correct
5 Correct 41 ms 564 KB Output is correct
6 Execution timed out 3053 ms 1804 KB Time limit exceeded
7 Halted 0 ms 0 KB -