QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#80217 | #62. Examination | lmeowdn | 0 | 174ms | 19576kb | C++14 | 2.5kb | 2023-02-23 09:22:23 | 2023-02-23 09:22:26 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
#define sgn(x) ((x)&1?-1:1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
return x*w;
}
const int N=1e5+9,lim=1e9;
int n,m,s[N],t[N],a[N],b[N],c[N],ans[N];
struct node {int id,tp,x,y;} f[N<<1];
bool cmp(const node &a,const node &b) {return a.x==b.x?(a.tp<b.tp):(a.x>b.x);}
namespace SegT {
int ls[N<<5],rs[N<<5],tot=1,s[N<<1],rt=1;
void init() {
rep(i,1,tot) ls[i]=rs[i]=s[i]=0;
tot=rt=1;
}
void insert(int &p,int l,int r,int x) {
if(!p) p=++tot; s[p]++; if(l==r) return; int mid=l+r>>1;
if(x<=mid) insert(ls[p],l,mid,x); else insert(rs[p],mid+1,r,x);
}
int leq(int p,int l,int r,int x) {
if(!p) return 0; if(l==r) return s[p]; int mid=l+r>>1;
if(x<=mid) return leq(ls[p],l,mid,x); else return s[ls[p]]+leq(rs[p],mid+1,r,x);
}
int geq(int p,int l,int r,int x) {
if(!p) return 0; if(l==r) return s[p]; int mid=l+r>>1;
if(x<=mid) return s[rs[p]]+geq(ls[p],l,mid,x); else return geq(rs[p],mid+1,r,x);
}
}
void work() {
SegT::init();
sort(f+1,f+n+m+1,cmp);
rep(i,1,n+m) {
if(f[i].tp==0) SegT::insert(SegT::rt,0,lim,f[i].y);
else if(f[i].tp==1) ans[f[i].id]+=SegT::geq(SegT::rt,0,lim,f[i].y);
else if(f[i].tp==2) ans[f[i].id]+=SegT::leq(SegT::rt,0,lim,f[i].y);
else if(f[i].tp==3) ans[f[i].id]-=SegT::leq(SegT::rt,0,lim,f[i].y);
else assert(0);
}
}
signed main() {
n=read(), m=read();
rep(i,1,n) s[i]=read(), t[i]=read();
rep(i,1,m) a[i]=read(), b[i]=read(), c[i]=max(read(),a[i]+b[i]);
rep(i,1,n) f[i]=(node){i,0,s[i],s[i]+t[i]};
rep(i,1,m) f[i+n]=(node){i,1,a[i],c[i]};
work();
rep(i,1,n) f[i]=(node){i,0,s[i],s[i]+t[i]};
rep(i,1,m) f[i+n]=(node){i,2,c[i]-b[i]+1,c[i]-1};
work();
rep(i,1,n) f[i]=(node){i,0,s[i],t[i]};
rep(i,1,m) f[i+n]=(node){i,3,c[i]-b[i]+1,b[i]-1};
work();
rep(i,1,m) printf("%lld\n",ans[i]);
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 2
Accepted
time: 1ms
memory: 3596kb
input:
10 10 28 2 78 81 39 79 61 31 36 99 90 5 20 55 91 4 48 19 80 7 52 43 78 64 65 171 34 68 124 37 80 161 53 19 123 49 58 109 95 46 30 45 48 60 47 13 54 64 30 144
output:
1 0 2 0 1 1 0 1 3 1
result:
ok 10 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
10 10 6 67 36 99 13 45 100 87 60 72 55 41 62 92 55 39 90 22 0 99 34 89 79 17 17 23 60 26 171 29 88 190 32 71 98 20 29 192 50 7 34 14 21 139 54 35 103 86 91 1
output:
2 7 1 0 4 0 6 2 3 0
result:
ok 10 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
10 10 67 72 94 99 34 22 1 71 68 18 90 94 29 44 98 61 46 9 94 76 73 36 11 30 26 75 5 85 112 38 35 111 39 72 143 6 64 130 31 24 134 82 86 188 80 20 151 91 32 62
output:
4 5 2 5 3 4 5 1 4 3
result:
ok 10 lines
Test #4:
score: -2
Wrong Answer
time: 2ms
memory: 3608kb
input:
10 10 667489048 282547819 694873877 525794923 605957229 147658688 928289876 455560133 465507205 531350815 397977066 913356070 351069660 834164613 611261253 238522918 683770744 737447844 351350094 473152918 514777487 599392520 569824365 137189600 455145855 1628925058 608994260 433029864 1934471803 80...
output:
4 5 3 1 6 1 10 5 1 1
result:
wrong answer 1st lines differ - expected: '1', found: '4'
Subtask #2:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 174ms
memory: 19576kb
input:
100000 100000 26753 11234 32815 62591 34318 93262 77179 57605 88208 33327 48449 99060 42403 58561 85715 7001 2418 90938 77409 6957 546 83283 53957 8374 49470 1483 65866 64950 4269 8745 19041 85833 22344 90706 92926 35603 54697 75311 72601 66401 77598 8193 3751 54202 32710 5877 23835 38264 34381 3338...
output:
3392 12465 20237 13565 11736 1182147 4108 33065 27851 26019 23511 12295 30617 229 20830 1461 3465 17020 36047 23196 1222712 24530 13442 8259 24433 733 10411 20119 15897 1154920 27339 1149671 46246 61350 520 59415 6149 798 2836 4628 14774 1125133 38231 7313 39010 14774 27553 20182 82757 35655 3811 29...
result:
wrong answer 6th lines differ - expected: '28514', found: '1182147'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%