QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#383008 | #3746. 千万别用树套树 | ucup-team1251 | WA | 395ms | 23272kb | C++17 | 1.6kb | 2024-04-08 20:53:14 | 2024-04-08 20:53:15 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
typedef pair<int,int>PII;
typedef array<int,3>ar;
typedef pair<int,double>PID;
typedef pair<string,string>PSS;
typedef pair<PII,int>PPI;
const ull mask = std::chrono::steady_clock::now().time_since_epoch().count();
const int N=2e5+5;
const int M=1e9+7;
const int base=131;
ull shift(ull x) //树哈希:映射函数 使用ull自然溢出
{
x ^= mask;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
x ^= mask;
return x;
}
int tr[10][N];
int n;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int w,int ran)
{
for(;x<=n;x+=lowbit(x))
{
tr[ran][x]+=w;
}
}
int get(int x,int ran)
{
int ans=0;
for(;x>0;x-=lowbit(x))
{
ans+=tr[ran][x];
}
return ans;
}
int en[N][10];
int st[N][10];
void solve()
{
int n,m;
while(cin>>n>>m)
{
int cnt=0;
for(int i=1;i<=m;i++)
{
int op,l,r;
cin>>op>>l>>r;
if(op==1)
{
cnt++;
add(l,1,1);
add(n-r+1,1,2);
if(r-l+1<=3)
{
en[r][r-l+1]++;
st[l][r-l+1]++;
}
en[r][4]++;
st[l][4]++;
}
else
{
int l1=get(l-1,1);
int r1=get(n-(r+1)-1,2);
int ne=cnt-l1-r1;
for(int i=l;i<=r;i++)
{
int ll=i-l+1;
int sum=0;
for(int k=1;k<=ll;k++)
{
sum+=en[i][k];
}
ne-=en[i][4]-sum;
ne-=st[i][4];
}
ne+=st[l][r-l+1];
cout<<ne<<"\n";
}
}
for(int i=1;i<=n;i++)
{
for(int k=1;k<=5;k++) en[i][k]=0,st[i][k]=0,tr[k][i]=0;
}
}
}
signed main()
{
ios::sync_with_stdio(0);
// cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while(t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 395ms
memory: 23272kb
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:
6 8 8 14 14 16 18 18 20 21 26 26 30 30 31 31 33 34 34 34 35 35 35 35 36 39 40 43 44 44 45 45 46 49 49 50 50 50 51 52 52 52 54 56 56 56 56 56 57 57 57 57 61 63 63 63 63 63 63 63 64 65 65 65 65 65 65 67 68 68 68 68 71 72 72 75 75 75 75 77 77 77 77 79 80 81 81 81 88 88 88 90 90 90 93 96 96 96 96 97 98 ...
result:
wrong answer 1st numbers differ - expected: '2', found: '6'