QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#382707 | #3746. 千万别用树套树 | ucup-team1251 | WA | 280ms | 11608kb | C++20 | 2.6kb | 2024-04-08 17:58:28 | 2024-04-08 17:58:28 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define buff ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
class ST
{
public:
ST(int x = 1000010)
{
n = x;
sza = 0;
int np = getsize(n);
sg.assign(np, 0);
stm.assign(np, 0);
}
ST(vector<ll>& aa, int x = -1)
{
a = aa;
if(x == -1)
n = a.size() - 1;
else
n = x;
sza = a.size();
int np = getsize(n);
sg.assign(np, 0);
stm.assign(np, 0);
build(1, n);
}
void update(int p, ll x)
{
_update(p, p, x, 1, n);
}
void update(int l, int r, ll x)
{
_update(l, r, x, 1, n);
}
ll query(int p)
{
return _query(p, p, 1, n);
}
ll query(int l, int r)
{
if(l > r)return 0;
return _query(l, r, 1, n);
}
protected:
void _update(int L, int R, ll x, int l, int r, int p = 1)
{
stm[p] += x * (R - L + 1);
if(L <= l && r <= R)
{
sg[p] += x;
return;
}
int mid = (l + r) >> 1;
if(R <= mid)
_update(L, R, x, l, mid, p << 1);
else if(L > mid)
_update(L, R, x, mid + 1, r, p << 1 | 1);
else
{
_update(L, mid, x, l, mid, p << 1);
_update(mid + 1, R, x, mid + 1, r, p << 1 | 1);
}
}
ll _query(int L, int R, int l, int r, int p = 1)
{
if(L <= l && r <= R)
return stm[p];
ll ret = sg[p] * (R - L + 1);
int mid = (l + r) >> 1;
if(R <= mid)
ret += _query(L, R, l, mid, p << 1);
else if(L > mid)
ret += _query(L, R, mid + 1, r, p << 1 | 1);
else
{
ret += _query(L, mid, l, mid, p << 1);
ret += _query(mid + 1, R, mid + 1, r, p << 1 | 1);
}
return ret;
}
private:
int n;
int sza;
vector<ll>a0;
vector<ll>& a = a0;
vector<ll>stm, sg;
unsigned int getsize(unsigned int x)
{
unsigned int xx = x;
xx |= xx >> 1;
xx |= xx >> 2;
xx |= xx >> 4;
xx |= xx >> 8;
xx |= xx >> 16;
if(x == ((xx + 1) >> 1))
return (xx + 1);
else
return ((xx + 1) << 1);
}
void build(int l, int r, int p = 1)
{
if(l == r)
{
if(l < sza)
stm[p] = a[l];
else
stm[p] = 0;
return;
}
int mid = (l + r) >> 1;
build(l, mid, p << 1);
build(mid + 1, r, p << 1 | 1);
stm[p] = stm[p << 1] + stm[p << 1 | 1];
}
};
int main()
{
buff;
int n, q;
while(cin >> n >> q)
{
ST st(n + 10);
ST st2(n + 10);
while(q--)
{
int op, l, r;
cin >> op >> l >> r;
if(op == 1)
{
st.update(l, 1);
st.update(r+1, -1);
//st2.update(l, -1);
//st2.update(r+1, 1);
}
else if(op == 2)
{
cout << st.query(1, r)/* - max(st2.query(1, r),0LL),0LL)*/ << '\n';
}
}
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 280ms
memory: 11608kb
input:
100000 100000 1 48500 63742 1 43673 89780 1 6471 44388 1 68054 71541 1 30056 91431 1 49687 70537 2 46899 46900 1 5165 57954 1 85892 88481 2 18060 18062 2 45289 45289 1 18927 67848 1 17389 96139 1 63451 92197 1 15473 87341 1 15162 15744 1 76728 99645 2 48730 48731 2 20886 20888 1 9756 67424 1 23175 4...
output:
2 2 3 7 5 8 9 4 6 2 11 13 13 10 13 15 9 10 14 16 17 16 16 15 2 4 11 6 11 12 23 9 26 3 28 20 12 12 22 30 5 27 6 29 10 14 27 6 17 15 9 30 20 34 7 36 15 8 32 16 21 40 19 2 1 12 12 39 37 13 19 20 1 9 37 1 41 40 20 34 45 43 27 30 47 29 13 50 41 44 29 35 38 53 2 46 54 36 56 58 45 32 42 26 52 42 60 1 4 25 ...
result:
wrong answer 511th numbers differ - expected: '123', found: '124'