oj.uz

Submission #128049

# Submission time Handle Problem Language Result Execution time Memory
128049 2019-07-10T11:16:53 Z claudy Street Lamps (APIO19_street_lamps) C++14
20 / 100
 270 ms 22268 KB 
//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# define LOCAL
# define sim template < class c
# define ris return * this
# define dor > debug & operator <<
# define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define show(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int gcd(int a, int b)
{
if(b) return gcd(b,a%b);
return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int L = 500;

int n,q;
string s;
int f[1 << 19],x[1 << 19],ans[1 << 19],mx[1 << 19];
vector<int>vec[1 << 19];

void upd(int i)
{
	for(;i <= n;i += i & (-i)) ans[i] += 1;
}

int qry(int i)
{
	int x = 0;
	for(;i;i -= (i & (-i))) x += ans[i];
	return x;
}

void UPD(int pos,int val)
{
	int block = pos / L;
	mx[block] = max(mx[block],val);
	f[pos] = val;
}

int last(int l,int r)
{
	int blockl = l / L;
	blockl++;
	int ans = 0;
	for(int i = l;i <= min(r,blockl * L);i++) ans = max(ans,f[i]);
	int blockr = r / L;
	for(int i = r;i >= max(l,blockr * L);i--) ans = max(ans,f[i]);
	blockr--;
	for(int i = blockl;i <= blockr;i++) ans = max(ans,mx[i]);
	return ans;
}

int32_t main(){_
	//freopen("input","r",stdin);
	cin >> n >> q;
	cin >> s;
	for(int i = 1;i <= n;i++)
	{
		if(s[i - 1] == '1') upd(i);
	}
	for(int i = 1;i <= q;i++)
	{
		string op;
		cin >> op;
		if(op[0] == 't')
		{
			cin >> x[i];
			UPD(x[i],i);
			upd(x[i]);
		}
		else
		{
			int l;
			int r;
			cin >> l >> r;
			r--;
			if(qry(r) - qry(l - 1) == r - l + 1)
			{
				cout << i - last(l,r) << '\n';
			}
			else cout << "0\n";
			
		}
	}
	return 0;
}

Compilation message

street_lamps.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 12664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 14152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12664 KB Output is correct
2 Correct 14 ms 12664 KB Output is correct
3 Correct 14 ms 12664 KB Output is correct
4 Correct 14 ms 12664 KB Output is correct
5 Correct 102 ms 20208 KB Output is correct
6 Correct 127 ms 21640 KB Output is correct
7 Correct 138 ms 22232 KB Output is correct
8 Correct 268 ms 22236 KB Output is correct
9 Correct 95 ms 16504 KB Output is correct
10 Correct 104 ms 16888 KB Output is correct
11 Correct 107 ms 17016 KB Output is correct
12 Correct 133 ms 19560 KB Output is correct
13 Correct 270 ms 22268 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12664 KB Output is correct
2 Incorrect 15 ms 12664 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 12664 KB Output isn't correct
2 Halted 0 ms 0 KB -