Submission #434681

#	Time	Username	Problem	Language	Result	Execution time	Memory
434681		fcmalkcin	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	1851 ms	35628 KiB

xorsum

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<db,db> pd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"

const ll maxn=1e3+10;
const ll mod =1e9+7 ;
const ll base=1e13;
ll a[maxn];
ll l[maxn*maxn];
ll r[maxn*maxn];
ll x[maxn*maxn];
ll gt[maxn];
ll gtv[maxn];
ll mul(ll a,ll n)
{
    if (n==0)
        return 1;
    if (n==1)
        return a;
    ll t=mul(a,n/2);
    if (n%2==0)
        return (t*t)%mod;
    return ((t*t)%mod*a)%mod;
}
void setup()
{
    gt[0]=1;
    for (int i=1; i<maxn; i++)
    {
        gt[i]=(gt[i-1]*i)%mod;
    }
    gtv[maxn-1]=mul(gt[maxn-1],mod-2);
    for (int i=maxn-2; i>=0; i--)
    {
        gtv[i]=(gtv[i+1]*(i+1))%mod;
    }
}
ll nck(ll n,ll k)
{
    if (n<k)
        return 0;
    return ((gt[n]*gtv[k])%mod*gtv[n-k])%mod;
}
vector<vector<ll>> dpl;
vector<vector<ll>> dpr;
vector<vector<ll>> dpb;

const int root = 3, MOD = (119<<23)+1; // 998244353
// For p < 2^30 there is also e.g. (5<<25, 3), (7<<26, 3)
/// (479<<21, 3) and (483<<21, 5). Last two are > 10^9.
const int MX = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool ckmin(T& a, const T& b)
{
    return b < a ? a = b, 1 : 0;
}
template<class T> bool ckmax(T& a, const T& b)
{
    return a < b ? a = b, 1 : 0;
}
int pct(int x)
{
    return __builtin_popcount(x);
}
int bits(int x)
{
    return 31-__builtin_clz(x);    // floor(log2(x))
}
int cdiv(int a, int b)
{
    return a/b+!(a<0||a%b == 0);    // division of a by b rounded up, assumes b > 0
}
int fstTrue(function<bool(int)> f, int lo, int hi)
{
    hi ++;
    assert(lo <= hi); // assuming f is increasing
    while (lo < hi)   // find first index such that f is true
    {
        int mid = (lo+hi)/2;
        f(mid) ? hi = mid : lo = mid+1;
    }
    return lo;
}
template<class T> void remDup(vector<T>& v)
{
    sort(all(v));
    v.erase(unique(all(v)),end(v));
}
// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
template<class T> void re(T& x)
{
    cin >> x;
}
void re(db& d)
{
    str t;
    re(t);
    d = stod(t);
}
void re(ld& d)
{
    str t;
    re(t);
    d = stold(t);
}
template<class H, class... T> void re(H& h, T&... t)
{
    re(h);
    re(t...);
}
template<class A> void re(complex<A>& c)
{
    A a,b;
    re(a,b);
    c = {a,b};
}
template<class A, class B> void re(pair<A,B>& p)
{
    re(p.f,p.s);
}
template<class A> void re(vector<A>& x)
{
    trav(a,x) re(a);
}
template<class A, size_t SZ> void re(array<A,SZ>& x)
{
    trav(a,x) re(a);
}
// TO_STRING
#define ts to_string
str ts(char c)
{
    return str(1,c);
}
str ts(bool b)
{
    return b ? "true" : "false";
}
str ts(const char* s)
{
    return (str)s;
}
str ts(str s)
{
    return s;
}
template<class A> str ts(complex<A> c)
{
    stringstream ss;
    ss << c;
    return ss.str();
}
str ts(vector<bool> v)
{
    str res = "{";
    F0R(i,sz(v)) res += char('0'+v[i]);
    res += "}";
    return res;
}
template<size_t SZ> str ts(bitset<SZ> b)
{
    str res = "";
    F0R(i,SZ) res += char('0'+b[i]);
    return res;
}
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v)   // containers with begin(), end()
{
    bool fst = 1;
    str res = "{";
    for (const auto& x: v)
    {
        if (!fst)
            res += ", ";
        fst = 0;
        res += ts(x);
    }
    res += "}";
    return res;
}
template<class A, class B> str ts(pair<A,B> p)
{
    return "("+ts(p.f)+", "+ts(p.s)+")";
}
// OUTPUT
template<class A> void pr(A x)
{
    cout << ts(x);
}
template<class H, class... T> void pr(const H& h, const T&... t)
{
    pr(h);
    pr(t...);
}
void ps()
{
    pr("\n");    // print w/ spaces
}
template<class H, class... T> void ps(const H& h, const T&... t)
{
    pr(h);
    if (sizeof...(t))
        pr(" ");
    ps(t...);
}
// DEBUG
void DBG()
{
    cerr << "]" << endl;
}
template<class H, class... T> void DBG(H h, T... t)
{
    cerr << ts(h);
    if (sizeof...(t))
        cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
// FILE I/O
void setIn(string s)
{
    freopen(s.c_str(),"r",stdin);
}
void setOut(string s)
{
    freopen(s.c_str(),"w",stdout);
}
void unsyncIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}
void setIO(string s = "")
{
    unsyncIO();
    // cin.exceptions(cin.failbit);
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s))
    {
        setIn(s+".in"), setOut(s+".out");    // for USACO
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    setup();
    ll n, q;
    cin>> n;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    cin>> q;
    for (int i=1; i<=q; i++)
    {
        cin>>l[i]>>r[i]>>x[i];
    }
    ll ans=0;
    for (int t=0; t<7; t++)
    {
        for (int k=0; k<7; k++)
        {
            dpl=vector<vector<ll>>(n+3,vector<ll>(n+3,0));
            dpr=vector<vector<ll>>(n+3,vector<ll>(n+3,0));
            dpb=vector<vector<ll>>(n+3,vector<ll>(n+3,0));

            const auto add = [&] (vector<vector<ll>> &dp,ll x,ll y,ll x1,ll y1)
            {
                dp[x][y]++;
                dp[x1+1][y]--;
                dp[x][y1+1]--;
                dp[x1+1][y1+1]++;
            };
            for (int i=1; i<=q; i++)
            {
                bool chk1=(x[i]&(1ll<<t));
                bool chk2=(x[i]&(1ll<<k));
                if (chk1&&chk2)
                {
                    add(dpb,l[i],l[i],r[i],r[i]);
                    add(dpr,1,l[i],l[i]-1,r[i]);
                    add(dpl,l[i],r[i]+1,r[i],n);
                }
                else if (chk1)
                {
                    add(dpl,l[i],1,r[i],n);
                }
                else if (chk2)
                {
                    add(dpr,1,l[i],n,r[i]);
                }
            }
            for (int i=1; i<=n; i++)
            {
                for (int j=1; j<=n; j++)
                {
                    dpb[i][j]+=dpb[i-1][j];
                    dpb[i][j]+=dpb[i][j-1];
                    dpb[i][j]-=dpb[i-1][j-1];
                    dpl[i][j]+=dpl[i-1][j];
                    dpl[i][j]+=dpl[i][j-1];
                    dpl[i][j]-=dpl[i-1][j-1];
                    dpr[i][j]+=dpr[i-1][j];
                    dpr[i][j]+=dpr[i][j-1];
                    dpr[i][j]-=dpr[i-1][j-1];
                }
            }
            const auto get = [&] (ll x,ll parity) ->ll
            {
                 if (x==0) return (parity==0);
                 return (mod+1)/2;
            };
            for (ll i=1; i<=n; i++)
            {
                for (ll j=i; j<=n; j++)
                {
                    ll nw=(1ll<<(t))*i*(n-j+1)*(1ll<<k);
                    if (i!=j)
                        nw=(nw*2)%mod;
                     ll pt=min(1ll,a[i]&(1ll<<t));
                     ll pt1=min(1ll,a[j]&(1ll<<k));
                     for (int t1=0;t1<=1;t1++)
                     {
                          for (int t2=0;t2<=1;t2++)
                          {
                              for (int t3=0;t3<=1;t3++)
                              {
                                  if (((pt^t1^t3)==1)&&((pt1^t2^t3)==1))
                                  {
                                       ans=(ans+(((get(dpl[i][j],t1)*get(dpr[i][j],t2))%mod*get(dpb[i][j],t3))%mod*nw)%mod)%mod;
                                  }
                              }
                          }
                     }
                }
            }
        }
    }
    for (int i=1;i<=q;i++)
    {
        ans=(ans*2)%mod;
    }
    cout <<ans;
}

Compilation message (stderr)

xorsum.cpp: In function 'void setIn(std::string)':
xorsum.cpp:277:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  277 |     freopen(s.c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
xorsum.cpp: In function 'void setOut(std::string)':
xorsum.cpp:281:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  281 |     freopen(s.c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp: In function 'int main()':
xorsum.cpp:308:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  308 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp:309:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  309 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 30 / 30
• Subtask 9: 8 / 8