QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #123815 | #4407. 回 | NOI_AK_ME | Compile Error | / | / | C++23 | 11.0kb | 2023-07-13 18:17:39 | 2023-07-13 18:17:42 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-07-13 18:17:42]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2023-07-13 18:17:39]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
int n, m;
unsigned ans[1000010];
constexpr int 1000000 = 1e6;
struct bit {
unsigned c[1000010];
int last[1000010], ts;
void upd(int p, unsigned k) {
for(; p ^ 1000001; p += p & -p) {
if(last[p] != ts) last[p] = ts, c[p] = 0;
c[p] += k;
}
}
unsigned qry(int p) {
unsigned ans = 0;
for(; p; p -= p & -p) ans += last[p] == ts ? c[p] : 0;
return ans;
}
void clear() {
++ts;
}
};
namespace S1 {
bit ds[2][4];
constexpr int cov[22][5] = {
{0,0,2,0,0},
{0,0,0,0,6},
{1,0,0,0,6},
{1,0,1,0,9},
{1,0,2,0,3},
{0,0,1,0,7},
{0,0,3,0,-1},
{0,0,0,1,-7},
{1,0,1,1,-6},
{0,0,1,1,0},
{0,0,2,1,3},
{1,0,0,1,-9},
{0,0,1,2,-3},
{1,0,0,2,3},
{0,0,0,2,0},
{0,0,0,3,1},
{0,1,1,0,-9},
{0,1,2,0,-3},
{0,1,0,0,-6},
{0,1,1,1,6},
{0,1,0,1,9},
{0,1,0,2,-3}
};
int cnt;
struct oper {
int o, x, y, z, w;
}a[1000010], b[1000010];
vector<int> Vz;
void emplace_update(int x, int y, int d, int w) {
a[++cnt] = {0, x - d + 1, y - d + 1, 0, w};
a[++cnt] = {0, x + d + 1, y + d + 1, 0, -w};
}
void emplace_query(int x1, int y1, int x2, int y2, int id) {
a[++cnt] = {1, x2, y2, 0, id};
a[++cnt] = {-1, x1 - 1, y2, 0, id};
a[++cnt] = {-1, x2, y1 - 1, 0, id};
a[++cnt] = {1, x1 - 1, y1 - 1, 0, id};
}
void calc() {
for(int i = 1; i <= cnt; ++i) b[i] = a[i];
auto upd = [&] (int i) {
static unsigned powerx[2], powery[4];
powerx[0] = powery[0] = 1;
for(int x = 1; x < 2; x ++) powerx[x] = powerx[x - 1] * a[i].x;
for(int y = 1; y < 4; y ++) powery[y] = powery[y - 1] * a[i].y;
for(int x = 0; x < 2; x ++) {
for(int y = 0; y < 4; y ++) {
ds[x][y].upd(a[i].z, powerx[x] * powery[y] * a[i].w);
}
}
};
auto qry = [&] (int i) {
static unsigned powerx[2], powery[4];
powerx[0] = powery[0] = 1;
for(int x = 1; x < 2; x ++) powerx[x] = powerx[x - 1] * a[i].x;
for(int y = 1; y < 4; y ++) powery[y] = powery[y - 1] * a[i].y;
unsigned ans = 0;
static unsigned ask[2][4];
for(int x = 0; x < 2; x ++) {
for(int y = 0; y < 4; y ++) {
ask[x][y] = ds[x][y].qry(a[i].z);
}
}
for(int c = 0; c < 22; c ++) if(cov[c][4]) {
ans += powerx[cov[c][0]] * powery[cov[c][2]] * ask[cov[c][1]][cov[c][3]] * cov[c][4];
}
return ans;
};
auto clear = [&] {
for(int x = 0; x < 2; x ++) {
for(int y = 0; y < 4; y ++) ds[x][y].clear();
}
};
function<void(int, int)> cdq = [&] (int l, int r) {
if(l == r) return ;
int mid = l + r >> 1;
cdq(l, mid), cdq(mid + 1, r);
clear();
for(int i = l, j = mid + 1; j <= r; j ++) if(a[j].o) {
while(i <= mid && a[i].y <= a[j].y) {
if(!a[i].o) upd(i);
i ++;
}
ans[a[j].w] += a[j].o * qry(j);
}
inplace_merge(a + l, a + mid + 1, a + r + 1, [&] (oper x, oper y) {
return x.y < y.y;
});
};
cdq(1, cnt);
for(int i = 1; i <= cnt; i ++) a[i] = b[i];
}
void work() {
for(int i = 1; i <= cnt; i ++) {
a[i].z = a[i].x - a[i].y;
Vz.emplace_back(a[i].z);
}
sort(Vz.begin(), Vz.end());
Vz.erase(unique(Vz.begin(), Vz.end()), Vz.end());
for(int i = 1; i <= cnt; i ++) {
a[i].z = lower_bound(Vz.begin(), Vz.end(), a[i].z) - Vz.begin() + 1;
}
calc();
for(int i = 1; i <= cnt; i ++) swap(a[i].x, a[i].y);
for(int i = 1; i <= cnt; i ++) {
a[i].z = Vz.size() - a[i].z + 1;
if(a[i].o) a[i].z --;
}
calc();
}
}
namespace S2 {
bit ds[4][4];
constexpr int cov1[15][5] = {
{0,0,2,0,3},
{0,0,3,0,1},
{0,0,1,0,2},
{0,0,2,1,-3},
{0,0,1,1,-6},
{0,0,0,1,-2},
{0,0,1,2,3},
{0,0,0,2,3},
{0,0,0,3,-1},
{0,1,2,0,-3},
{0,1,1,0,-9},
{0,1,0,0,-6},
{0,1,1,1,6},
{0,1,0,1,9},
{0,1,0,2,-3}
};
constexpr int cov2[22][5] = {
{2,0,1,0,-3},
{2,0,0,0,-3},
{1,0,2,0,-3},
{1,0,1,0,-6},
{3,0,0,0,-1},
{1,0,0,0,-2},
{2,0,0,1,3},
{1,0,1,1,6},
{1,0,0,1,6},
{1,0,0,2,-3},
{1,1,0,0,6},
{0,1,1,0,-3},
{0,1,0,0,-4},
{1,1,1,0,6},
{2,1,0,0,3},
{1,1,0,1,-6},
{0,1,0,1,3},
{1,2,0,0,-3},
{0,2,0,0,-3},
{0,2,1,0,-3},
{0,2,0,1,3},
{0,3,0,0,1}
};
constexpr int cov3[6][5] = {
{1,0,2,0,-3},
{1,0,1,0,-9},
{1,0,0,0,-6},
{1,0,1,1,6},
{1,0,0,1,9},
{1,0,0,2,-3}
};
int cnt;
struct oper {
int o, x, y, z, w;
}a[1000010], b[1000010];
vector<int> Vz;
vector<int> Vy;
void emplace_update(int x, int y, int d, int w) {
a[++cnt] = {0, x + d, y - d + 1, 0, w};
a[++cnt] = {0, x - d, y + d + 1, 0, -w};
}
void emplace_query(int x1, int y1, int x2, int y2, int id) {
a[++cnt] = {1, x1, y2, 0, id};
a[++cnt] = {-1, x2 + 1, y2, 0, id};
a[++cnt] = {-1, x1, y1 - 1, 0, id};
a[++cnt] = {1, x2 + 1, y1 - 1, 0, id};
}
void calc1() {
for(int i = 1; i <= cnt; i ++) b[i] = a[i];
auto upd = [&] (int i) {
static unsigned powerx[2], powery[4];
powerx[0] = powery[0] = 1;
for(int x = 1; x < 2; ++x) powerx[x] = powerx[x - 1] * a[i].x;
for(int y = 1; y < 4; ++y) powery[y] = powery[y - 1] * a[i].y;
for(int x = 0; x ^ 2; ++x)
for(int y = 0; y ^ 4; ++y)
ds[x][y].upd(a[i].z, powerx[x] * powery[y] * a[i].w);
};
auto qry = [&] (int i) {
static unsigned powerx[2], powery[4];
powerx[0] = powery[0] = 1;
for(int x = 1; x < 2; ++x) powerx[x] = powerx[x - 1] * a[i].x;
for(int y = 1; y < 4; ++y) powery[y] = powery[y - 1] * a[i].y;
unsigned ans = 0;
static unsigned ask[2][4];
for(int x = 0; x ^ 2; ++x)
for(int y = 0; y ^ 4; ++y)
ask[x][y] = ds[x][y].qry(a[i].z);
for(int c = 0; c < 15; c ++) if(cov1[c][4])
ans += powerx[cov1[c][0]] * powery[cov1[c][2]] * ask[cov1[c][1]][cov1[c][3]] * cov1[c][4];
return ans;
};
auto clear = [&] {
for(int x = 0; x < 2; x ++) {
for(int y = 0; y < 4; y ++) ds[x][y].clear();
}
};
function<void(int, int)> cdq = [&] (int l, int r) {
if(l == r) return ;
int mid = l + r >> 1;
cdq(l, mid), cdq(mid + 1, r);
clear();
for(int i = l, j = mid + 1; j <= r; j ++) if(a[j].o) {
while(i <= mid && a[i].y <= a[j].y) {
if(!a[i].o) upd(i);
i ++;
}
ans[a[j].w] += a[j].o * qry(j);
}
inplace_merge(a + l, a + mid + 1, a + r + 1, [&] (oper x, oper y) {
return x.y < y.y;
});
};
cdq(1, cnt);
for(int i = 1; i <= cnt; i ++) a[i] = b[i];
}
void calc2() {
for(int i = 1; i <= cnt; i ++) b[i] = a[i];
auto upd = [&] (int i) {
static unsigned powerx[4], powery[3];
powerx[0] = powery[0] = 1;
for(int x = 1; x < 4; x ++) powerx[x] = powerx[x - 1] * a[i].x;
for(int y = 1; y < 3; y ++) powery[y] = powery[y - 1] * a[i].y;
for(int x = 0; x < 4; x ++)
for(int y = 0; y < 3; y ++)
ds[x][y].upd(a[i].z, powerx[x] * powery[y] * a[i].w);
};
auto qry = [&] (int i) {
static unsigned powerx[4], powery[3];
powerx[0] = powery[0] = 1;
for(int x = 1; x < 4; x ++) powerx[x] = powerx[x - 1] * a[i].x;
for(int y = 1; y < 3; y ++) powery[y] = powery[y - 1] * a[i].y;
unsigned ans = 0;
static unsigned ask[4][3];
for(int x = 0; x < 4; x ++)
for(int y = 0; y < 3; y ++)
ask[x][y] = ds[x][y].qry(a[i].z);
for(int c = 0; c < 22; c ++) if(cov2[c][4])
ans += powerx[cov2[c][0]] * powery[cov2[c][2]] * ask[cov2[c][1]][cov2[c][3]] * cov2[c][4];
return ans;
};
auto clear = [&] {
for(int x = 0; x < 4; x ++)
for(int y = 0; y < 3; y ++) ds[x][y].clear();
};
function<void(int, int)> cdq = [&] (int l, int r) {
if(l == r) return ;
int mid = l + r >> 1;
cdq(l, mid), cdq(mid + 1, r);
clear();
for(int i = l, j = mid + 1; j <= r; j ++) if(a[j].o) {
while(i <= mid && a[i].x >= a[j].x) {
if(!a[i].o) upd(i);
i ++;
}
ans[a[j].w] += a[j].o * qry(j);
}
inplace_merge(a + l, a + mid + 1, a + r + 1, [&] (oper x, oper y) {
return x.x > y.x;
});
};
cdq(1, cnt);
for(int i = 1; i <= cnt; i ++) a[i] = b[i];
}
void calc3() {
for(int i = 1; i <= cnt; i ++) b[i] = a[i];
auto upd = [&] (int i) {
static unsigned powerx[2], powery[3];
powerx[0] = powery[0] = 1;
for(int x = 1; x < 2; x ++) powerx[x] = powerx[x - 1] * a[i].x;
for(int y = 1; y < 3; y ++) powery[y] = powery[y - 1] * a[i].y;
for(int x = 0; x < 1; x ++)
for(int y = 0; y < 3; y ++)
ds[x][y].upd(a[i].z, powerx[x] * powery[y] * a[i].w);
};
auto qry = [&] (int i) {
static unsigned powerx[2], powery[3];
powerx[0] = powery[0] = 1;
for(int x = 1; x < 2; x ++) powerx[x] = powerx[x - 1] * a[i].x;
for(int y = 1; y < 3; y ++) powery[y] = powery[y - 1] * a[i].y;
unsigned ans = 0;
static unsigned ask[2][3];
for(int x = 0; x < 2; x ++)
for(int y = 0; y < 3; y ++)
ask[x][y] = ds[x][y].qry(a[i].z);
for(int c = 0; c < 6; c ++) if(cov3[c][4])
ans += powerx[cov3[c][0]] * powery[cov3[c][2]] * ask[cov3[c][1]][cov3[c][3]] * cov3[c][4];
return ans;
};
auto clear = [&] {
for(int x = 0; x < 1; x ++)
for(int y = 0; y < 3; y ++) ds[x][y].clear();
};
function<void(int, int)> cdq = [&] (int l, int r) {
if(l == r) return ;
int mid = l + r >> 1;
cdq(l, mid), cdq(mid + 1, r);
clear();
for(int i = l, j = mid + 1; j <= r; j ++) if(a[j].o) {
while(i <= mid && a[i].x < a[j].x) {
if(!a[i].o) upd(i);
i ++;
}
ans[a[j].w] += a[j].o * qry(j);
}
inplace_merge(a + l, a + mid + 1, a + r + 1, [&] (oper x, oper y) {
return x.x < y.x;
});
};
cdq(1, cnt);
for(int i = 1; i <= cnt; i ++) a[i] = b[i];
}
void work() {
for(int i = 1; i <= cnt; i ++) {
a[i].z = a[i].x + a[i].y;
Vz.emplace_back(a[i].z);
Vy.emplace_back(a[i].y);
}
sort(Vz.begin(), Vz.end());
Vz.erase(unique(Vz.begin(), Vz.end()), Vz.end());
sort(Vy.begin(), Vy.end());
Vy.erase(unique(Vy.begin(), Vy.end()), Vy.end());
for(int i = 1; i <= cnt; i ++) {
a[i].z = lower_bound(Vz.begin(), Vz.end(), a[i].z) - Vz.begin() + 1;
}
for(int i = 1; i <= cnt; i ++) {
a[i].z = Vz.size() - a[i].z + 1;
}
calc1();
for(int i = 1; i <= cnt; i ++) {
a[i].z = Vz.size() - a[i].z + 1;
if(a[i].o) a[i].z --;
}
calc2();
for(int i = 1; i <= cnt; i ++)
a[i].z = lower_bound(Vy.begin(), Vy.end(), a[i].y) - Vy.begin() + 1;
calc3();
}
}
unsigned encode(unsigned x) {
assert(~x & 1);
x >>= 1;
unsigned ans = 0;
for(int i = 0; i ^ 30; ++i) {
int c = x >> i & 1;
if(c) {
x -= 1u << i + 1;
ans |= 1u << i;
}
}
return ans;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> m;
int tot = 0;
for(int i = 1; i <= m; i ++) {
int o;
cin >> o;
if(o == 1) {
int x, y, d, w;
cin >> x >> y >> d >> w;
S1::emplace_update(x, y, d, w);
S2::emplace_update(x, y, d, -w);
} else {
int x1, x2, y1, y2;
cin >> x1 >> x2 >> y1 >> y2;
tot ++;
S1::emplace_query(x1, y1, x2, y2, tot);
S2::emplace_query(x1, y1, x2, y2, tot);
}
}
S1::work();
S2::work();
for(int i = 1; i <= tot; i ++)
cout << encode(ans[i]) << '\n';
return 0;
}
詳細信息
answer.code:5:15: error: expected unqualified-id before numeric constant
5 | constexpr int 1000000 = 1e6;
| ^~~~~~~